[Project Euler] Problem 18

원문: Problem 18

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

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

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

아래 삼각형의 꼭대기에서 시작해서 행의 인접한 수들로 움직일 때, 꼭대기부터 바닥까지 가장 큰 총합은 23이다.

3
7 4
2 4 6
8 5 9 3

즉, 3 + 7 + 4 + 9 = 23 이다.

아래 삼각형의 꼭대기부터 바닥까지 가장 큰 총합을 찾아라:

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

참고: 오직 16384개의 경로만 있기 때문에, 모든 경로를 시도하여 문제를 푸는 것이 가능하다. 그러나 Problem 67은 100개의 행을 포함하는 삼각형에 대한 문제이다. 그것은 brute force(단순하게 모든 경우를 시도하는 방법)으로는 풀 수 없다. 그러므로 현명한 방법이 필요하다. ;o)

문제에 써 있듯이 brute force, 즉 단순하게 모든 경로를 탐색하는 방법으로는 Problem 67를 풀 수 없다. 그래서 이 문제 풀이를 계속 미루고 있었는데, 최근에 DP(Dynamic Programming, 동적 계획법)을 배우고 나서, 이를 여기에 적용 시킬 수 있었다.

Python

동적 계획법으로 푼 방식은 아주 간단하다. 자료구조에서 트리(tree) 개념을 조금 섞어서 풀었는데, 이 삼각형을 Full Binary Tree와 비슷하게 보고, 위에서부터 순서를 매기면 부모와 왼쪽 아이의 인덱스는 부모 행(1부터 시작)만큼 차이가 나고, 오른쪽 아이는 부모 행 + 1 만큼 차이가 난다.

따라서 Full Binary Tree이므로 1행짜리 리스트에 저장을 쭉 해두고 아래서부터 위로 탐색을 했다. 이때, 탐색 방법은 가장 큰 값을 고르기 위해서 각 행마다 아래 행의 두 숫자 중에서 큰 값을 선택하여 더해주는 방법을 이용했다. 그러면 루트(꼭대기 값)에는 어떤 루트의 가장 큰 값이 들어가게 된다. (왜냐하면 가장 큰 값을 계속 골랐으므로)

그리고 brute force, O(2 ^ 행)과 비교해서 걸리는 시간은 O(행)이다. 쉽게 말하면 brute force는 16384 (2 ^ 14)를 모두 탐색하지만 이의 경우 45번(9행까지의 모든 요소들)만 검색하면 답을 구할 수 있다.

#! /usr/bin/env python3

data = open("input.txt", "r")

tree = []
row = 0 # 행 개수
for line in data:
    tree += [int(x) for x in line.rstrip('\n').split(' ')]
    row += 1

data.close()

while row > 0:
    row -= 1 # 마지막 행의 윗 행부터 시작
    first = (row - 1) * row // 2 # 그 행의 첫번째 인덱스
    for i in range(row):
        right = tree[first + i + row + 1]
        left = tree[first + i + row]
        tree[first + i] += right if right > left else left

print(tree[0]) # 루트가 가장 큰 값

접기