[BOJ 2169] 로봇 조종하기

다이나믹 프로그래밍 분류 문제이다.

 

 

 

만약 dp를 2차원 배열로 정의하면 문제가 해결되지 않는다.

 

 

 

dp[i][j]의 값이 만들어질 때, 직전 출발지가 왼쪽에서 왔는지, 오른쪽에서 왔는지, 위쪽에서 왔는지에 따라 값이 달라져야 하기 때문에 3차원 배열이 필요하다.

 

 

 

 

해설코드(C++).

 

 

#include <iostream>
#define MIN -987654321
using namespace std;
 
int N, M;
int arr[1001][1001];
bool check[1001][1001] = {false};
int dp[1001][1001][3];
 
int func(int i, int j, int dir){
    if(dp[i][j][dir] != MIN)
        return dp[i][j][dir];
        
    if(i == N && j == M)
        return arr[i][j];
 
    if(i + 1 <= N &&check[i + 1][j] == false)
    {
        check[i + 1][j] = true;
        dp[i][j][dir] = func(i + 1, j, 0);
        check[i + 1][j] = false;
    }    
        
    if(j + 1 <= M && check[i][j + 1] == false){
        check[i][j + 1] = true;
        dp[i][j][dir] = max(dp[i][j][dir], func(i, j + 1, 1));
        check[i][j + 1] = false;
    }
    
    if(j - 1 >= 1 && check[i][j - 1] == false){
        check[i][j - 1] = true;
        dp[i][j][dir] =  max(dp[i][j][dir], func(i, j - 1, 2));
        check[i][j - 1] = false;
    }
    
    dp[i][j][dir] += arr[i][j];
    return dp[i][j][dir];
}
 
int main() {
    cin >> N >> M;
    for(int i = 1; i <= N ;i++){
        for(int j = 1; j <= M; j++){
            cin >> arr[i][j];
            for(int k = 0; k < 3; k++)
                dp[i][j][k] = MIN;
        }
    }
    
    check[1][1] = true;
    cout << func(1, 1, 0) << endl;
    return 0;
}