[EP 018] 삼각형 배열에서 지나간 수의 합을 최대로 하는 경로를 구하기

문제에서는 경로를 다 구할 필요는 없었고, 경로합의 최대값만 구하면 되었다.

 

 

중간에 어떤 노드까지 거슬러 올 수 있는 모든 경로의 최대값을 알 수 있다고 하자. 한 줄에 대해서 다 안다고 하자.

그럼 그 윗줄의 어떤 노드 A까지 거슬러 올 수 있는 모든 경로의 최대값은, 그 A 아래의 두 노드 각각의 최대값과 A노드 값의 합, 두가지 경우 중에서 결정된다.

 

#!/usr/bin/env python

# http://projecteuler.net
# Problem 18
# Find a top-to-bottom path which makes the path-sum maximum

# Author : DwYoon
# Date   : 2020

# I reduce the triangle from the bottom. Each cell of the last line is designed
# to contain the maximum path sum from the bottom to that node.

"""
       3
     4   1
    1  5  2
   / \/ \/ \
   1  2  3  4

      3
     4 1
    /\ /\
    3 8 6

       3
      / \ 
     12 9

      15
"""

import pprint

triangle = [
    [75],
    [95, 64],
    [17, 47, 82],
    [18, 35, 87, 10],
    [20, 4, 82, 47, 65],
    [19, 1, 23, 75, 3, 34],
    [88, 2, 77, 73, 7, 63, 67],
    [99, 65, 4, 28, 6, 16, 70, 92],
    [41, 41, 26, 56, 83, 40, 80, 70, 33],
    [41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
    [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
    [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
    [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
    [63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
    [4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23],
]

while len(triangle) != 1:
    last_line = triangle[-1]

    for i, v in enumerate(triangle[-2]):
        if last_line[i] < last_line[i + 1]:
            bigger = last_line[i + 1]
        else:
            bigger = last_line[i]
        triangle[-2][i] += bigger
    triangle = triangle[:-1]
    # pprint.pprint(triangle)
print(triangle[0][0])