BOJ 2169:: 로봇 조종하기

2018년 1월 21일

동적 계획법 문제입니다. 먼저 각 지역의 가치를 $val(i,j)$라 하고, $up$, $left$, $right$를 다음과 같이 정의합니다.

한 마디로 정리하자면 어느 방향에서 $(i,j)$로 들어오는지에 따라 분류하자는 겁니다. 만약 왼쪽, 위, 오른쪽이 없는 경우엔 그렇게 방문이 불가능하므로 최댓값은 음의 무한대(−INF)입니다.

점화식을 세웁시다. $up$은 쉽습니다. $(i-1,j)$를 방문해서 얻을 수 있는 가치의 최댓값에다 $val(i,j)$를 더해주면 됩니다.

\[ up(i,j) = \max[up(i-1,j), \ left(i-1,j), \ right(i-1,j)] + val(i,j) \]

$left$를 계산하려면 $(i,j-1)$을 방문해서 얻을 수 있는 가치의 최댓값을 알아야 하는데, 이건 $up(i,j-1)$과 $left(i,j-1)$ 중 큰 쪽입니다. 같은 곳을 두 번 이상 방문할 수 없기 때문에 $right(i,j-1)$은 고려하지 않아도 됩니다.

\[ left(i,j) = \max[up(i,j-1), \ left(i,j-1)] + val(i,j) \]

마찬가지로 $right$는

\[ right(i,j) = \max[up(i,j+1), \ right(i,j+1)] + val(i,j) \]

점화식이 나왔으니 이제 초기값을 구합시다. $right(0,j)$는 당연히 -INF이고, $up(0,j)$는 $j=0$이면 $val(0,0)$, 아니면 -INF입니다. $left(0,j)$는 $val(0,0)$부터 $val(0,j)$까지의 합입니다.

재귀함수와 메모이제이션으로 구현한다면 문제 없지만 반복문으로 구현할 땐 순서가 매우 중요합니다. $up$을 먼저 구하고 $left$, $right$를 나중에 구해야 하며 $left$는 왼쪽에서 오른쪽으로, $right$는 오른쪽에서 왼쪽으로 구하고 $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;
}
PS