(참고: 이 문제는 81번 문제의 좀 더 어려운 버전입니다)
아래와 같은 5×5 행렬이 있습니다. 맨 왼쪽 열의 아무 곳에서나 출발하여 위/아래/오른쪽으로만 움직이면서 맨 오른쪽 열까지 갈 때, 빨갛게 표시된 경로의 합이 994로 가장 작습니다.
 |
|  |
31KB짜리 파일 matrix.txt에는 80×80 행렬의 정보가 들어있습니다. 위와 같은 방법으로 이 행렬의 맨 왼쪽 열에서 출발하여 맨 오른쪽 열까지 갈 때, 경로 합의 최소값은 얼마입니까?
http://euler.synap.co.kr/prob_detail.php?id=82 이건 문제 링크
여기서 생각 할 수 있는건 일단 첫째줄이랑 마지막 도착지점에선 위 아래로 움직이진 않을꺼니까 그 앞에껄로 전부 더해 줄 수 있음
근데 그 다음부터는 이걸 어떻게 풀어야할지 감이 안잡힘
여러가지 생각해봣는데 도무지 감이 안잡혀서 건들지도 못하고있음
답은 필요없으니 힌트좀
위/아래/오른쪽 으로만 움직이니까 첫번째줄에서부터 우측 끝까지 제일 주변값중 제일 작은거만 골라서 찾아가서 더하고 그다음 두번째줄부터 출발해서 우측 제일 끝까지 가는데 주변값중 제일 작은것만 골라서 찾아가며 더하고 비교하면되지않음?
ㄴㄴ 그게 안됨 간단하게 보면 최소값 탐색이 무의미하다는건 그런 알고리즘으로는 위나 아래로만 쭉쭉 물릴 가능성도 있고 지금 여기 숫자가 4자리니까 최대값이 9999인데 9999 다음에 1이 연달아 있으면 그런것도 최소값 탐색으로는 못찾아냄 9999를 보자마자 생까버리니까
min(i,j) 를 (i,j)지점에서의 최소값이라고 하면 min(i,j)는 다음과 같이 계산됨 => d(i,j) + { MIN ( min(i-1,j), min(i,j-1), min(i,j+1) ) } memoization 적용하면 속도 이득 볼듯.