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개 경로밖에 없기 때문에, 모든 경로를 시도하는 방법으로 해결할 수 있다. 그러나, 100개 행이 있는 삼각형에서 동일한 방식으로 답을 구하는 67번 문제는 브루트 포스(brute force) 방법으로 해결할 수 없고, 현명한 방법이 필요하다.
--------------------------------------------------------------------------
모든 경로를 한번씩 다 운영해보고 최대값을 구하는 것이 가장 간단한 방법인데 문제의 마지막에서 다른 방법을 찾아보기를 권하고 있어 고민을 했던 문제이다.
고민해서 적용한 방법은 위에서 내려오는 방법으로 계산하는 것이 아니고, 밑에서 위로 올라가면서 계산하면 16384개 경로를 비교하는 것 보다는 조금 적은 복잡도를 가지는 방법이 가능했다. 14번째 행 첫번째 숫자인 63에 더해질 수 있는 숫자는 4와 62인데 이 중 더 큰 62를 더하는 방법을 반복해 나가면 숫자의 갯수만큼 반복해 나가는 것으로 답을 구할 수 있다.