이번 문제는 백준 골드 5 내려가기 문제이다.
차근차근 문제를 한 번 읽어보자.
아래로 내려가며 점수를 얻는 게임인데, 내려가는 위치가 정해져 있다.
현재 위치에서 두 칸 떨어져 있는 칸으로는 내려갈 수 없는 모양이다.
이 게임에서 얻을 수 있는 최대, 최소 점수를 계산하는 것이 문제다.
완전탐색?
가장 먼저 단순하게 시뮬레이션으로 이 문제를 풀 수 있는지 생각해보자.
최대 100000줄 까지 내려갈 수 있으며, 열은 3열로 고정된다.
이 때 만약 모든 경우의 수를 찾으며 내려간다면 시간이 얼마나 걸릴까?
위에서 어떤 칸을 선택했고, 어디로 내려오냐에 따라 값이 달라지게 되는데,
그 경우를 모두 다 살펴보려면 줄 별 경우의 수에 10만 승을 한 것이 된다.
이건 상식적으로 불가능한 풀이니, 다른 방법을 생각해보자.
DP?
위에서 부터 내려올 때, 이전 칸까지의 최대 최소를 저장하면서 내려온다면?
2번 칸의 최대, 최소 = 1번 칸의 최대 최소 + 현재 칸 정보 가 될 수 있다.
이 점을 이용한다면, 시간을 어느정도 줄일 수 있지 않을까 싶다.
이 방식을 우리는 DP(동적 프로그래밍) 이라고 했었다.
2번 칸에 있을 때 어떻게 최대, 최소를 구할 수 있는지 부터 생각해보자.
(2,1)칸의 최대, 최소는(1,1)이나(1,2)와 연산될 것이다.(2,2)칸은(1,1), (1,2), (1,3)모두와 연산이 가능하다.(2,3)칸은(1,2), (1,3)와 연산이 가능하다.
위의 사실을 미루어보아, 1열 2열 3열은 계산되는 칸이 정해져 있음을 알 수 있다.
이를 분기문으로 구분하여 최대, 최소를 갱신하며 내려간다면 어떨까?
단, 최소와 최대를 따로 갱신하여 최소끼리 최대끼리 연산을 하면서 내려가야 한다.
우선 아래와 같이 배열을 선언해보자.
int dp[100000][3][2];
// dp의 마지막 칸은 [최대, 최소]게임판과 동일한 크기인데, 최대 최소만 따로 저장할 수 있도록 했다.
다음과 같이 배열을 초기화 한다.
void init_dp() {
dp[0][0][0] = board[0][0];
dp[0][0][1] = board[0][0];
// 첫 번째 칸 최대, 최소
dp[0][1][0] = board[0][1];
dp[0][1][1] = board[0][1];
// 두 번째 칸 최대, 최소
dp[0][2][0] = board[0][2];
dp[0][2][1] = board[0][2];
// 세 번째 칸 최대, 최소
}DP 문제를 풀 때, 초기값(기저)을 설정하는 것도 매우 중요하다!
가장 먼저 첫 칸에 대한 정보를 DP 배열로 옮겨 저장한다.
이제 본격적으로 Memoization을 시작해보자.
for (int i = 1; i < num; i++) {
for (int j = 0; j < 3; j++) {
if (j == 0) {
dp[i][j][0] = max(dp[i - 1][j][0] + board[i][j], dp[i-1][j+1][0] + board[i][j]);
dp[i][j][1] = min(dp[i - 1][j][1] + board[i][j], dp[i-1][j+1][1] + board[i][j]);
}
if (j == 1) {
dp[i][j][0] = max(dp[i - 1][j - 1][0] + board[i][j],
max(dp[i - 1][j][0] + board[i][j],
dp[i - 1][j + 1][0] + board[i][j]));
dp[i][j][1] = min(dp[i - 1][j - 1][1] + board[i][j],
min(dp[i - 1][j][1] + board[i][j],
dp[i - 1][j + 1][1] + board[i][j]));
}
if (j == 2) {
dp[i][j][0] = max(dp[i - 1][j][0] + board[i][j], dp[i - 1][j - 1][0] + board[i][j]);
dp[i][j][1] = min(dp[i - 1][j][1] + board[i][j], dp[i - 1][j - 1][1] + board[i][j]);
}
}
}위에서 말했던대로, 3칸 밖에 되지 않으니 분기문을 통해 구현했다.
각 칸으로 올 수 있는 칸과의 연산을 통해 최대, 최소를 갱신하며 진행한다.
하지만 결과는 메모리 초과.. 아무래도 DP 배열의 크기가 너무 큰 모양이다.
기존 board 배열도 큰데 DP 배열까지 커서 메모리 초과가 발생한듯 하다.
DP 배열의 크기를 줄일 방법은 없을까?
생각을 곰곰히 해보니, board 배열에서 정보를 다 가지고 있다.
그럼 굳이 DP 배열에서 100000개의 행을 모두 저장할 필요가 있을까?
아, 그럼 DP 배열은 1개의 행으로 3열만 저장해서 값을 갱신하도록 하자!
잠깐, 그러면 DP 배열 내의 값이 계속 갱신되지 않을까?
이 부분이 잠시 문제였지만, 변수를 새로 선언하여 저장했다 옮기는 식으로 구현했다.
최종 통과 코드는 아래와 같다.
for (int i = 1; i < num; i++) {
max_temp1 = dp[0][0], min_temp1 = dp[0][1];
max_temp2 = dp[1][0], min_temp2 = dp[1][1];
max_temp3 = dp[2][0], min_temp3 = dp[2][1];
for (int j = 0; j < 3; j++) {
if (j == 0) {
dp[j][0] = max(max_temp1 + board[i][j], max_temp2 + board[i][j]);
dp[j][1] = min(min_temp1 + board[i][j], min_temp2 + board[i][j]);
}
if (j == 1) {
dp[j][0] = max(max_temp1 + board[i][j],
max(max_temp2 + board[i][j],
max_temp3 + board[i][j]));
dp[j][1] = min(min_temp1 + board[i][j],
min(min_temp2 + board[i][j],
min_temp3 + board[i][j]));
}
if (j == 2) {
dp[j][0] = max(max_temp2 + board[i][j], max_temp3 + board[i][j]);
dp[j][1] = min(min_temp2 + board[i][j], min_temp3 + board[i][j]);
}
}
}뭔가 이런 전형적인 나 DP에요~ 하고 티내는 문제는 이제 익숙한 것 같다.
다른 개념이 섞여있거나, DP임을 티를 내지 않는 문제가 정말 어렵다.
좀 더 많이 연습을 해보도록 하자.