[백준 2169번] 로봇 조종하기 (C++)

https://www.acmicpc.net/problem/2169

 

꽤 생각할 것이 있는 다이나믹프로그래밍 문제였다. 

 

먼저 이 왜 다이나믹 프로그래밍인가? 

 

1.  N이 약 1000으로 백트래킹으로 모든 경우의 수를 다 진행할 시 당연히 시간초과에 걸린다.

2. 한 지점에 도착할 수 있는 경우의 수가 정해져있다.

3. 2번에 의해 큰 문제를 작은 문제로 쪼갤 수 있다. 

 

이 근거로 다이나믹 프로그래밍이라고 유출할 수 있겠다.

 

그렇다면 어떻게 풀어야할까? 처음에는 0,0 에서 시작하는 재귀 + DP를 생각했다. 그러나 문제가 있었다.

 

이 문제는 왼쪽과 오른쪽으로 이동을 할 수 있다. 

 

1 2 3

4 5 6

7 8 9

 

라고 할 때 재귀를 진행하면 1번에서 2번으로 이동하면 2번은 다시 1번으로 이동할 수 있다. 그렇다고 visited같은 것을 사용하면 Dp가 아니게 되버린다. 그저 DFS, BFS와 다를게 없어진다.

 

그래서 경우를 나누어 생각한다.

1. 오른쪽, 아래만 가능한 경우

2. 왼쪽, 아래만 가능한 경우

 

어차피 1번 행은 왼쪽에서만 더할 수 있으므로 DP값을 초기설정할 수 있다. 

위 예제를 사용하면 

1 3 9

 

그리고 첫번째 경우를 생각해보자

오른쪽 혹은 아래만 갈 수 있으므로 

1 3 9

5 10 16

 

이 될 것이다. 이번에는 두번째 경우를 생각해보자

 

 

 

1 3 9

24 20 15

 

이 될 것이다. 

 

아하.. 그리고 실제 DP값은 이 둘 중에 더 큰 값이 가장 큰 값을 가지는 경로가 될 것이다.

 

이제 점화식을 새울 수 있을 것 같다.

 

 

각 인덱스에 따른 예외처리까지 적용하여 코드로 바꿔보면

for(int i = 1; i < N; i++){        
        for(int j = 0; j < M; j++){
            if(j == 0){
                leftDp[i][j] = max(leftDp[i][j], Dp[i - 1][j] + value[i][j]);
            } else{
                leftDp[i][j] = max(leftDp[i][j - 1] + value[i][j], Dp[i - 1][j] + value[i][j]);
            }
        }

        for(int j = M - 1; j > -1; j--){
            if(j == M - 1){
                rightDp[i][j] = max(rightDp[i][j], Dp[i - 1][j] + value[i][j]);
            }else{
                rightDp[i][j] = max(rightDp[i][j + 1] + value[i][j], Dp[i - 1][j] + value[i][j]);
            }
        }
        for(int j = 0; j < M; j++){
            Dp[i][j] = max(leftDp[i][j], rightDp[i][j]);
        }
    }

 

이렇게 정의된다.

 

#include <iostream>
#define MAX 1001
using namespace std;

int value[MAX][MAX];
int leftDp[MAX][MAX];
int rightDp[MAX][MAX];
int Dp[MAX][MAX];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    cin >> N >> M;

    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> value[i][j];
            Dp[i][j] = -100001;
            leftDp[i][j] = -100001;
            rightDp[i][j] = -100001;
        }
    }

    Dp[0][0] = value[0][0];
    for(int i = 1; i < M; i++){
        Dp[0][i] = Dp[0][i - 1] + value[0][i];
    }
    int idx = 0;
    for(int i = 1; i < N; i++){        
        for(int j = 0; j < M; j++){
            if(j == 0){
                leftDp[i][j] = max(leftDp[i][j], Dp[i - 1][j] + value[i][j]);
            } else{
                leftDp[i][j] = max(leftDp[i][j - 1] + value[i][j], Dp[i - 1][j] + value[i][j]);
            }
        }

        for(int j = M - 1; j > -1; j--){
            if(j == M - 1){
                rightDp[i][j] = max(rightDp[i][j], Dp[i - 1][j] + value[i][j]);
            }else{
                rightDp[i][j] = max(rightDp[i][j + 1] + value[i][j], Dp[i - 1][j] + value[i][j]);
            }
        }
        for(int j = 0; j < M; j++){
            Dp[i][j] = max(leftDp[i][j], rightDp[i][j]);
        }
    }
    cout << Dp[N - 1][M - 1] << '\n';
}