BOJ 2169:: 로봇 조종하기

http://acmicpc.net/problem/2169

동적 계획법 문제입니다.

먼저 각 지역을 가치를 $\textrm{Val}$ 배열에 저장하고, $\textrm{Up, Left, Right}$ 배열을 다음과 같이 정의합니다.

  • $\textrm{Up}(i, j)$ : $(i-1, j)$를 방문한 후 $(i, j)$를 방문하여 얻을 수 있는 가치의 최댓값
  • $\textrm{Left}(i, j)$ : $(i, j-1)$을 방문한 후 $(i, j)$를 방문하여 얻을 수 있는 가치의 최댓값
  • $\textrm{Right}(i, j)$ : $(i, j+1)$을 방문한 후 $(i, j)$를 방문하여 얻을 수 있는 가치의 최댓값

한 마디로 정리하자면 어느 방향에서 $(i, j)$로 들어오느냐에 대해 따로 생각하자는 겁니다. 만약 왼쪽, 위, 오른쪽이 없는 경우엔 그렇게 방문이 불가능하므로 최댓값은 음의 무한대($-\textrm{INF}$)입니다.
그럼 점화식을 세워야죠. $\textrm{Up}$은 쉽습니다. $(i-1, j)$를 방문해서 얻을 수 있는 가치의 최댓값에다 $(i, j)$의 가치를 더해주면 됩니다. 즉,

\[ \textrm{Up}(i, j) = \max \{\textrm{Up}(i-1, j), \textrm{Left}(i-1, j), \textrm{Right}(i-1, j) \} + \textrm{Val}(i, j) \]

문제는 $\textrm{Left}$와 $\textrm{Right}$입니다. $\textrm{Left}$ 먼저 생각해봅시다. $(i, j-1)$을 방문해서 얻을 수 있는 가치의 최댓값을 알아야 하는데, 이건 $\textrm{Up}(i, j-1)$과 $\textrm{Left}(i, j-1)$ 중 큰 쪽입니다. $\textrm{Right}(i, j-1)$를 빼는 이유는 $\textrm{Right}(i, j-1)$를 고려한다는 건 $(i, j)$를 방문한 다음 $(i, j-1)$을 방문하겠다는 것이므로, 같은 곳을 두 번 이상 방문하지 않는다는 조건 때문에 $(i, j-1)$에서 다시 $(i, j)$로 갈 수가 없습니다. 따라서 $\textrm{Right}(i, j-1)$을 빼야하고, 점화식은

\[ \textrm{Left}(i,j) = \max \{\textrm{Up}(i, j-1), \textrm{Left}(i, j-1) \} + \textrm{Val}(i,j) \]

마찬가지로 $\textrm{Right}$의 점화식은

\[ \textrm{Right}(i,j) = \max \{\textrm{Up}(i, j+1), \textrm{Right}(i, j+1) \} + \textrm{Val}(i, j) \]

점화식이 나왔으니 초기값을 구합니다. $\textrm{Right}(0, j)$는 당연히 $-\textrm{INF}$이고, $\textrm{Up}(0, j)$는 $j=0$이면 $(0, 0)$의 가치, 아니면 $-\textrm{INF}$, $\textrm{Left}(0, j)$는 $(0, 0)$부터 $(0, j)$까지 가치의 합입니다.

아래 코드는 Iterative DP로 구현했기 때문에 반복문 순서가 정말 중요합니다. $\textrm{Up}$을 제일 먼저 구하고, $\textrm{Left}$, $\textrm{Right}$ 순으로 구해야 하며 $\textrm{Left}$는 왼쪽에서 오른쪽으로, $\textrm{Right}$는 오른쪽에서 왼쪽으로 구하고 $\textrm{Up}$은 마음대로입니다.

#include<cstdio>
#include<algorithm>
 
#define INF 1000000000;
 
 
using namespace std;
 
int n, m;
int Val[1000][1000];
int Up[1000][1000], Left[1000][1000], Right[1000][1000];
 
 
int main(void) {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &Val[i][j]);
            
    Left[0][0] = Up[0][0] = Val[0][0];
    
    for (int j = 1; j < m; j++)
        Up[0][j] = -INF;
    for (int j = 1; j < m; j++)
        Left[0][j] = Left[0][j-1] + Val[0][j];
    for (int j = m-1; j >= 0; j--)
        Right[0][j] = -INF;
 
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < m; j++)
            Up[i][j] = max({Up[i-1][j], Left[i-1][j], Right[i-1][j]}) + Val[i][j];
        Left[i][0] = -INF;
        for (int j = 1; j < m; j++)
            Left[i][j] = max(Up[i][j-1], Left[i][j-1]) + Val[i][j];
        Right[i][m-1] = -INF;
        for (int j = m-2; j >= 0; j--)
            Right[i][j] = max(Up[i][j+1], Right[i][j+1]) + Val[i][j];
    }
    
    printf("%d", max(Left[n-1][m-1], Up[n-1][m-1]));
            
    return 0;
}