[C/C++] 백준 #2169 로봇 조종하기(동적 계획법)

#2169 문제는 동적 계획법을 이용했지만, 일반적인 동적 계획법은 한방향으로만 진행되는 경우에 주로 사용됩니다.  이 문제에서는 한곳의 값을 결정하기 위해서는 왼쪽, 오른쪽, 그리고 위라는 3군데 방향을 고려해야 하므로 좀 까다롭습니다.

 

문제의 링크입니다.

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

2169번: 로봇 조종하기

 

문제는 나사(NASA)의 로봇이 화성을 돌아다닐때, 최대한의 가치를 얻으면서 지역을 탐사하는 것입니다.

 

NASA Mars Rover @NASA

 

처음에 어떻게 짜야할까 고민하다가, 조금 복잡하게 만들었습니다.  dp라는 기본적인 동적 계획법에 의한 저장값을 저장할 때에 3개의 값을 저장하게 하였습니다.  dp[*][*][0] 은 위에서 온 값 중 최대값을 저장합니다.  dp[*][*][1] 은 왼쪽에서 온 값 중 최대값을 저장합니다.  dp[*][*][2] 는 오른쪽에서 온 값 중 최대값을 저장합니다.  이렇게 함으로써, 왼쪽과 오른쪽을 왔다갔다하면서 현재의 가치값이 증폭되는 것을 막았습니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2169 - Controlling a robot
//        - by Aubrey Choi
//        - created at 2019-12-05
//------------------------------------------------
#include <stdio.h>

int max(int a, int b) { return (a>b)?a:b; }
int max(int a, int b, int c) { a=(a>b)?a:b; return (a>c)?a:c; }
int main()
{
    int n, m, s, i, j;
    static int dp[1000][1000][3], t[1000][1000]; 
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++) for(j=0;j<m;j++)
    {
        scanf("%d",&s); t[i][j]=s; 
        dp[i][j][0]=-1000000000; dp[i][j][1]=-1000000000; dp[i][j][2]=-1000000000; 
    }
    for(i=1,dp[0][0][0]=t[0][0];i<m;i++) dp[0][i][0]=dp[0][i-1][0]+t[0][i];
    for(i=1;i<n;i++)
    {
        for(j=0;j<m;j++) dp[i][j][0]=max(dp[i-1][j][0], dp[i-1][j][1], dp[i-1][j][2])+t[i][j];
        for(j=1,dp[i][0][1]=dp[i][0][0];j<m;j++)
            dp[i][j][1]=max(dp[i][j-1][0], dp[i][j-1][1])+t[i][j];
        for(j=m-2,dp[i][m-1][2]=dp[i][m-1][0];j>=0;j--)
            dp[i][j][2]=max(dp[i][j+1][0], dp[i][j+1][2])+t[i][j];
    }
    printf("%d\n", max(dp[n-1][m-1][0], dp[n-1][m-1][1], dp[n-1][m-1][2]));
}