백준 2169 로봇 조종하기

이 문제는 로봇이 1,1에서 N,M까지 가는데 왼쪽,오른쪽,아래로 갈 수 있고 한번 방문한 곳은 못갈 때 최대 값을 구해야 하는 문제입니다.

 

N,M의 제한이 1000이므로 모든 경로를 다보는 것은 1000^3으로 불가능 합니다. 따라서 dp를 이용하여야 하는데

 

우선은 i,j에서 다음 경로로 이동 할 때 전에 어디서 왔느냐에 따라 갈 수 있는 곳이 제한 됩니다. 예를들어 

i,j의 값이 i,j-1에서 온 값이라면 왼쪽 이동이 불가능 합니다.

 

따라서 dp를 3차원배열로 만들고 풀었습니다.

 

dp[i][j][k] = i,j에서 이전에 k방향에서 왔을 때의 cost 

 

이후 쭉 돌면서 i,j에서 갈수 있는 값을 갱신 시켜 줍니다. 이때 각 행에 대해서 왼쪽에서 오른쪽으로 먼저 진행을 해주고

반대로 오른쪽에서 왼쪽으로도 진행을 해주어야 합니다

(왼쪽에서 오른쪽만 하면 오른쪽에서 왼쪽으로 온뒤 밑으로 내려가는 그런 상황을 체크 할 수 없습니다).

그래야 최대값이 들어갈 수 있습니다. 그림으로 그려보시면 이해가 될거라고 생각합니다.

 

그리고 주의할점은 각 칸에 들어있는 값의 절대값이 100이하 이므로 

초기 배열의 값을 -100000 보다 작은 값으로 다바꿔줘야 합니다. (1000*100 이므로) 

 

다음은 코드입니다.

 

#include <bits/stdc++.h>

using namespace std;

int cost[1010][1010];
int dp[1010][1010][3]; // 1,1에서 i,j 까지 k에서 왔을 때 최대 값 0은 왼쪽 1은 오른쪽 2는 아래로 내려옴

int main(void) {
    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++)
            for(int k = 0; k < 3; k++)
                dp[i][j][k] = -10000000;


    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++)
            cin >> cost[i][j];

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

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(j+1 < M) {
                dp[i][j+1][0] = max(dp[i][j+1][0], dp[i][j][0]+cost[i][j]);
                dp[i][j+1][0] = max(dp[i][j+1][0], dp[i][j][2]+cost[i][j]);
            }

            if(i+1 < N) {
                dp[i+1][j][2] = max(dp[i+1][j][2], dp[i][j][0]+cost[i][j]);
                dp[i+1][j][2] = max(dp[i+1][j][2], dp[i][j][1]+cost[i][j]);
                dp[i+1][j][2] = max(dp[i+1][j][2], dp[i][j][2]+cost[i][j]);
            }


            if(j-1 >= 0) {
                dp[i][j-1][1] = max(dp[i][j-1][1], dp[i][j][1]+cost[i][j]);
                dp[i][j-1][1] = max(dp[i][j-1][1], dp[i][j][2]+cost[i][j]);
            }
        }


        for(int j = M-1; j >= 0; j--) {
            if(j+1 < M) {
                dp[i][j+1][0] = max(dp[i][j+1][0], dp[i][j][0]+cost[i][j]);
                dp[i][j+1][0] = max(dp[i][j+1][0], dp[i][j][2]+cost[i][j]);
            }

            if(i+1 < N) {
                dp[i+1][j][2] = max(dp[i+1][j][2], dp[i][j][0]+cost[i][j]);
                dp[i+1][j][2] = max(dp[i+1][j][2], dp[i][j][1]+cost[i][j]);
                dp[i+1][j][2] = max(dp[i+1][j][2], dp[i][j][2]+cost[i][j]);
            }


            if(j-1 >= 0) {
                dp[i][j-1][1] = max(dp[i][j-1][1], dp[i][j][1]+cost[i][j]);
                dp[i][j-1][1] = max(dp[i][j-1][1], dp[i][j][2]+cost[i][j]);
            }
        }
    }
    int ans = 0;
    ans = max(dp[N-1][M-1][0], dp[N-1][M-1][2]);
    cout<<ans+cost[N-1][M-1];
    return 0;
}