BOJ - 2096 ) 내려가기

문제 해결 접근

 

별로 어렵지 않은 형태의 기본적인 동적 프로그래밍의 문제로 보인다. 입력받은 점수 행렬은 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]

 

한 행이 진행 될때마다, 이전 행렬의 합산 값을 비교하여 최소 혹은 최대의 값과 현재 행렬의 값을 더해준다. 

 

 

따라서 다음과 같이 코딩을 해주면...

 

 

 배열의 크기 때문에 메모리 초과가 일어난다. 따라서, 이를 방지하기 위하여 배열 크기의 조정이 필요하다. 최소값과 최대값을 갱신하여 주는 배열은 주어지는 N 값 만큼의 크기가 필요하지 않다. 즉, 주어진 N 만큼의 크기를 일일히 갱신하여 주는 것이 최종 값을 도출하는 데에 필요하지 않기 때문에 갱신을 위해 비교해야 하는 이전 행의 값을 저장하는 행과 갱신된 값을 저장하는 행 두가지가 필요하다. 이는 다음과 같이 표현이 가능하다.

 

d[1][0] = map[i][0] + max(d[0][0], d[0][1]);
d[1][1] = map[i][1] + max(d[0][0], max(d[0][1], d[0][2]));
d[1][2] = map[i][2] + max(d[0][1], d[0][2]);

d[0][0] = d[1][0];
d[0][1] = d[1][1];
d[0][2] = d[1][2];

dp[1][0] = map[i][0] + min(dp[0][0], dp[0][1]);
dp[1][1] = map[i][1] + min(dp[0][1], min(dp[0][0], dp[0][2]));
dp[1][2] = map[i][2] + min(dp[0][2], dp[0][1]);

dp[0][0] = dp[1][0];
dp[0][1] = dp[1][1];
dp[0][2] = dp[1][2];

 

최대값을 갱신하는 d[2][3] 행렬은, 이전의 행과 비교값을 d[1][0~2] 에 저장하고, 이를 다시 d[0][0~2] 의 값에 대입하여 초기화 해준다.