프로젝트 오일러 018

문제

18번 문제

삼각형을 따라 내려가면서 합이 최대가 되는 경로 찾기

사이냅소프트

최대합 경로를 역추적하기

편의상 삼각형을 가운데 정렬이 아닌 왼쪽 정렬이 되어 있다고 생각하겠습니다. 삼각 형의 특정 지점의 숫자까지 도달하는 경로는 바로 위의 숫자로부터 내려오거나, 윗줄 왼쪽 의 숫자로부터 내려오는 두 가지 경로만 존재할 것입니다. 즉 각 행의 각각의 숫자들은 위에서 내려오는 방법이 2가지 있습니다. 그리고 각 숫자의 지점에서 내려가는 방법도 두 가지 입니다.

맨 아랫줄에서 바로 위쪽, 그러니까 끝에서 두 번째 줄의 각 숫자의 지점까지 그 지점에 이르는 최대합 경로를 통해 다다랐다고 가정해봅시다. 당연하게도 각 숫자에서 왼쪽으로 가거간 오른쪽으로 가는 경우 중에서 큰 쪽으로 이동했을 때 맨 아랫줄의 최대합경로를 이루게 될 것입니다. 맨 아랫 줄의 모든 숫자에 대해 최대합 경로를 통해 이동했다면, 맨 아랫줄에서의 최대합이 가장 큰 숫자로 이어진 경로가 전체의 최대합 경로가 됩니다.

이 논리를 거꾸로 적용하면, 맨 아래 줄 15개 중 앞 14개와, 뒤 14개를 각각 14번째 줄과 더한 것 중 큰 값을 취하고, 다시 14개 중에서 앞 13개를 뒤 13개와 각각 더해서 큰 값을 취하는 식으로 줄여나가면 맨 윗줄에서 최대경로합의 합계를 얻게 됩니다.

이 과정은 아래와 같이 간단히 계산할 수 있고, 아주 빠른 시간 내에 끝납니다. 이 문제에서는 67번 문제의 예를 들면서 쉽게 끝나지 않을 것이라고 했는데, 같은 알고리듬으로 67번 문제 역시 간단하게 풀립니다.

s = """
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 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 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
"""

xs = [list(map(int, line.split())) for line in  s.strip().splitlines()]
a = xs[-1]
for line in xs[-2::-1]:
    x = map(sum, zip(a, line))
    y = map(sum, zip(a[1:], line))
    a = [max(*n) for n in zip(x, y)]
print(a[0])