맨 왼쪽 열에서 맨 오른쪽 열까지 가는 경로의 합이 최소인 경우는?

Problem 82

출제 일시 : 2012-04-26 19:27:33

(참고: 이 문제는 81번 문제의 좀 더 어려운 버전입니다)

아래와 같은 5×5 행렬이 있습니다. 맨 왼쪽 열의 아무 곳에서나 출발하여 위/아래/오른쪽으로만 움직이면서 맨 오른쪽 열까지 갈 때, 빨갛게 표시된 경로의 합이 994로 가장 작습니다.


13167323410318
20196342965150
630803746422111
537699497121956
80573252437331

31KB짜리 파일 matrix.txt에는 80×80 행렬의 정보가 들어있습니다. 위와 같은 방법으로 이 행렬의 맨 왼쪽 열에서 출발하여 맨 오른쪽 열까지 갈 때, 경로 합의 최소값은 얼마입니까?



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