공부공간

문제 해결 접근 별로 어렵지 않은 형태의 기본적인 동적 프로그래밍의 문제로 보인다. 입력받은 점수 행렬은 3개의 열을 가지며 항상 최대, 최소 값을 갱신하도록 알고리즘을 설계하여 준다. 해당 문제의 점화식은 다음과 같다. minDP[i][0] = min(minDP[i-1][0] , minDP[i-1][1]) + map[i][0] minDP[i][1] = min(minDP[i-1][0], min(minDP[i-1][1], minDP[i-1][2])) + map[i][1] minDP[i][2] = min(minDP[i-1][1] , minDP[i-1][2]) + map[i][2] 한 행이 진행 될때마다, 이전 행렬의 합산 값을 비교하여 최소 혹은 최대의 값과 현재 행렬의 값을 더해준다. 따라서 다음과 같이 ..