프로젝트 오일러 67번

67번 문제는 다음과 같다.

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 in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.

NOTE: It is not possible to try every route to solve this problem, as there are 2⁹⁹ altogether! If you could check one trillion (10¹²) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it.)

삼각형 모양으로 쌓여 있는 숫자들을 맨 위의 숫자부터 하나씩 더해가는데, 바로 아랫 줄의 이웃한 숫자들로만 더해 나갈 수 있다. 이때 그 합의 최댓값을 구하는 문제이다.

예를 들면, 보기에서 3 다음에 더할 수 있는 숫자는 바로 아랫줄의 3과 이웃한 숫자인 7 또는 4가 된다. 또한 두 번째 줄의 7 다음에 더할 수 있는 숫자는 바로 아랫 줄의 7과 이웃한 숫자인 2 또는 4가 된다. 이런 식으로 마지막 줄까지 숫자들을 하나씩 더해서 그 합을 구할 때, 그 합이 최대가 되는 경우는 3+7+4+9=23 이 된다.

예에서 보는 삼각형의 높이는 4이다. 이와 같이 삼각형의 높이가 높지 않다면 모든 가능한 경우의 합을 다 구해서 그 들의 최댓값을 구하면 되겠지만, triangle.txt 에 주어진 삼각형은 그 높이가 100이다. 문제에서 설명했듯이 모든 가능한 경우의 합을 모두 구하여 최댓값을 구한다면 어마어마한 시간이 걸릴 것이다. (1초에 1조개의 합을 구한다고 하더라도 200억년 정도가 걸린다. 우와~~~)

따라서 다른 알고리즘을 생각해 내야 한다. 내 경우는 다음과 같은 방법을 사용했다.

먼저 첫 번째 줄과 두 번째 줄을 한꺼번에 보면

\[3\]

\[ 7, \; 4\]

\[---\]

\[10, \; 7\]

이 되고, 다시 \(10, \;7\) 과 세 번째 줄 \( 2, \; 4,\; 6\) 을 같이 보면

\[10, \;7\]

\[2, \;4,\; 6\]

\[-----\]

\[12, \; 14,\; 13\]

이 된다. \(12, \; 14, \; 13\) 에서 \(14\) 의 자리에는 \(10+4\) 혹은 \(4+7\) 이 올 수 있었지만, 그 합이 더 큰 쪽을 선택하여 값을 결정한다.

마지막으로 \(12, \;14,\; 13\) 과 네 번째 줄 \(8,\; 5,\; 9,\; 3\) 을 같이 보면

\[12, \; 14,\; 13\]

\[ 8, \; \;5, \;\; 9, \;\; 3\]

\[-------\]

\[20, \; 19, \; 23,\; 16\]

이 된다. 이 경우에도 마찬가지로 \(19\) 의 자리에는 \(12+5\) 혹은 \(14+5\) 가 올 수 있었지만, 합이 더 큰 \(19\) 쪽을 선택하여 값을 결정하였으며, \(23\) 자리에는 \(14+9\) 혹은 \(13+9\) 가 올 수 있었지만, 합이 더 큰 \(23\) 쪽을 선택하여 값을 결정한 것이다.

결국 우리가 찾는 최댓값은 \(20, \;19, \;23, \;16\) 중 최대인 \(23\)이 된다.

삼각형의 높이가 100개일 때도 똑같은 방법으로 계산한다면 200억년이 아닌 눈 깜짝할 사이에 답을 구해낼 수 있다.