Boj 2169 로봇 조종하기 c++

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

 

 

문제

 

 

 

 

접근 & 풀이

 

 

현재 로봇이 있는 칸에 도달하기 위해서는 이전 상태가 3가지로 고정된다. 

1. 이전 행에서 한칸 아래로 이동한 경우

2. 이전 열에서 한칸 오른쪽으로 이동한 경우

3. 앞선 열에서 한칸 왼쪽으로 이동한 경우

 

1번, 2번, 3번의 값을 모두 저장해놓아야 다음 행을 초기화할 때 올바른 값을 계산할 수 있다.

즉, 상태정의를 위한 요소가 좌표, 이전 상태인 3차원 dp이다.

 

위칸에서 한칸 아래로 이동하는 경우에는 더이상 이전 행의 값들을 참조할 일이 없으므로, 1번, 2번, 3번 경우 중 최댓값만을 취하면 된다.

이전 열에서 한칸 오른쪽으로 이동한 경우에는 로봇은 이미 방문한 칸을 다시 방문할 수 없기 때문에 로봇의 진행방향은 중간에 바뀔 수 없다. 때문에, 로봇의 이전상태는 1번, 2번 뿐이다.

왼쪽으로 이동한 경우도 마찬가지이다. 이전상태는 위에서 이동한 경우와 왼쪽으로 이동한 경우 중 최댓값.

 

불가능한 경우는 inf 처리 해주는 것도 잊지 말아야 한다.

 

정답코드

 

#include <iostream>
#include <algorithm>
#define inf -999999999
using namespace std;

int dp[1020][1020][3], mp[1020][1020];
/*
  0 : 위쪽, 1 : 왼쪽, 2 : 오른쪽
*/

int main() {

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

    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= M; j++) {
            cin >> mp[i][j];
        }
    }

    for(int i = 0; i <= 1001; i++) {
        for(int j = 0; j <= 1001; j++) {
            for(int k = 0; k <= 2; k++) {
                dp[i][j][k] = inf;
            }
        }
    }

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

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

    cout << max(dp[N][M][0], dp[N][M][1]);
}