18. Maximum path sum I

1. 개요

문제는 이곳에서 확인할 수 있다. 숫자를 삼각형으로 쌓아놓고 위 층으로부터 한가지 길을 선택해 내려가면서 누적합을 구하되 가장 큰 값을 구하는 것이 목표이다. 단, 길 선택은 두 갈래 중의 하나만 가능하다. 예를 들면, 아래의 숫자 더미에서 최대값은 3 + 7 + 4 + 9 = 23이다. 

2. Ver 2.0

모든 경우의 수를 찾는 것은 간단한 방법이지만 숫자더미가 커질수록 비효율적인 방법이다. 층수가 충분히 많으면 내가 눈을 감을 때까지도 답을 찾지 못할 수도 있다. 그래서 1주일 가량 다른 방법을 생각해봤지만 결국 답을 찾지 못하고 구글링을 하였다. 

방법은 생각보다 훨씬 간단했다. 요는 위에서부터 내려가는 것이 아니라, 밑에서부터 올라가면서 최대값을 찾는 것 이었다. 즉, \(l\)번째 층의 \(i\)번째 원소를 \(l+1\)번째 층의 \(i\)번째, \(i+1\)번째 원소와 각각 더하여 그 중의 큰 값으로 바꾸면 된다. 이 과정을 \(l\)을 줄여나가면서 각 층의 원소에 대해서 수행하면 된다.

위의 숫자 더미를 예로 들어보자. 3번째 층의 첫번째 원소인 2를 4번째 층의 첫번째 원소인 8과 두번째 원소인 5와 각각 더하면 10과 7이다. 그러므로 3번째 층의 첫번째 원소를 10으로 바꾼다. 이 과정을 3번째 층의 나머지 원소 그리고 두번째, 첫번째 층에 대해서도 반복한다. 

# -*- coding: utf-8 -*-

str_data = """
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
""".split("\n")
str_data.pop(0)
str_data.pop()

int_data = []

while len(str_data) > 0:
    int_data.append([int(n) for n in str_data.pop(0).split(" ")])

temp_data = int_data.pop()

while len(int_data) > 0:
    max_data = int_data.pop()

    for k, v in enumerate(max_data):
        max_data[k] = max(v + temp_data[k], v + temp_data[k+1])
    temp_data = max_data

print(max_data[0])

답은 21124이다.

3. 마치며

나는 이 문제를 풀어나가는 과정을 보고 무척 놀랐다. 왜냐하면 이 문제는 우리가 삶을 어떻게 살아야 하는지에 대한 인사이트를 주기 때문이다. 즉, 어떤 문제를 해결하기 위해서는 시작이 아니라 끝에서 출발해야 한다는 점 말이다. 

우리는 어떠한 길을 선택해야 하는지 항상 고민한다. 무엇이 최선의 선택이며 결국 우리를 행복하게 할 것인지 고민하면서 말이다. 하지만 우리에겐 굉장히 많은 선택지가 있어 무엇을 선택해야 우리가 목표로 하는 것을 이룰지 알지 못한다. 이럴때 생각할 수 있는 해결책은, 우리가 그 목표를 이루었다고 가정하고 시간을 조금씩 거꾸로 되돌려 가면서, 그것을 이루기 위해서 무엇을 선택했을지 생각하는 것이다. 

물론 실제 삶에는 두가지보다 더 많은 선택지가 존재한다. 또한 불연속적인 도약 또는 추락이 있을 수도 있고 뜻하지 않은 행운 또는 불행이 있을 수도 있다. 그럼에도 불구하고 우리가 해야하는 것은, 우리가 목표를 이루었다고 생각하고 그것을 이루기 위해 했을 행동을 지금 하는 것이다.