Problem 67

출제 일시 : 2012-02-04 18:19:38

아래와 같은 삼각형의 꼭대기에서 인접한 숫자를 따라 내려가는 경로의 합을 계산해보면, 붉은 색으로 표시한 경우가 3 + 7 + 4 + 9 = 23으로 가장 큽니다.

3
7 4
2 4 6
8 5 9 3

텍스트 파일 triangle.txt (우클릭해서 다운로드)에는 100줄짜리 삼각형 숫자 데이터가 들어 있습니다. 꼭대기에서 바닥에 이르는 경로의 합 중 최대값은 얼마입니까?

참고: 이 문제는 18번 문제와 비슷하지만 훨씬 더 어려운 버전입니다. 이 문제를 풀려고 모든 경로를 계산하는 것은 가능하지 않은데, 경우의 수가 모두 299 이나 되기 때문입니다. 일 초에 1조 (1012)개의 경로를 계산할 수 있다고 해도, 모든 경우의 수를 계산하려면 200억년이 걸립니다. 이 문제를 해결할 수 있는 효율적인 알고리즘을 찾아보시기 바랍니다.



로그인 하시면 답안을 제출할 수 있고,
정답을 맞히신 분들은 댓글을 달거나 볼 수 있습니다.