BOJ 2169 로봇 조정하기

 

문제 링크 : https://www.acmicpc.net/problem/2169

2169번: 로봇 조종하기

 

1. dp 의 정의

좌표 ( i , j ) 에 진입하는 방식에 따라 다음 움직임이 제한된다. 즉, 진입 방향을 기록할 필요가 있다.

dir 은 진입 방향을 나타내는데 사용한다. (1, 1) 이 좌측 상단을 위미한다고 할 때,

dir=1 은 위에서 아래로, dir=0 은 오른쪽에서, dir=2는 왼쪽에서 진입을 나타낸다.

dp[i][j][dir]은 ( 1, 1 ) 에서 이동하여 dir 방향으로 ( i , j ) 로 진입했을 때, 얻을 수 있는 가치의 최댓값으로 정의한다.

 

2. 기저 사례 처리

가치의 최댓값을 구하기 위해 max 함수를 사용함을 상기하자.

따라서 발생할 수 없는 사례에 대해서는 dp 값을 엄청 작은 값으로 초기화한다.

 

#include<bits/stdc++.h>

using namespace std;
const int Inf=1e9+7;

int arr[1001][1001], dp[1001][1001][3];

int main(){
    int n,m; scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) for(int j=0;j<m;j++)
        scanf("%d",&arr[i][j]);
    
    dp[0][0][1]=arr[0][0];
    dp[0][0][0]=-Inf;
    dp[0][0][2]=-Inf;
    for(int i=1;i<m;i++) {
        dp[0][i][2]=max(dp[0][i-1][1],dp[0][i-1][2])+arr[0][i];
        dp[0][i][0]=dp[0][i][1]=-Inf;
    }

    for(int i=1;i<n;i++){
        for(int j=0;j<m;j++)
            dp[i][j][1]=arr[i][j]+max(dp[i-1][j][0], 
                                      max(dp[i-1][j][1],dp[i-1][j][2]));
        
        dp[i][0][2]=-Inf;
        for(int j=1;j<m;j++)
            dp[i][j][2]=arr[i][j]+max(dp[i][j-1][2],dp[i][j-1][1]);
        
        dp[i][m-1][0]=-Inf;
        for(int j=m-2;j>=0;j--)
            dp[i][j][0]=arr[i][j]+max(dp[i][j+1][0],dp[i][j+1][1]);
    }
    
    int ans=-Inf;
    for(int i=1;i<3;i++)
        ans=max(ans, dp[n-1][m-1][i]);
    printf("%d\n", ans);
}