콘텐츠로 건너뛰기
Home » 67

67

오일러 프로젝트 67

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

텍스트 파일 triangle.txt에는 100줄짜리 삼각형 수 데이터가 들어있습니다. 꼭대기에서 바닥에 이르는 경로의 합 중 최댓값은 얼마입니까?

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

https://euler.synap.co.kr/problem=67
더 보기 »오일러 프로젝트 67