BOJ 2169:: 로봇 조종하기

동적 계획법 문제입니다. 먼저 각 지역의 가치를 $v a l (i, j)$ 라 하고, $u p$ , $l e f t$ , $r i g h t$ 를 다음과 같이 정의합니다.

$u p (i, j)$ : $(i - 1, j)$ 를 방문한 후 $(i, j)$ 를 방문하여 얻을 수 있는 가치의 최댓값
$l e f t (i, j)$ : $(i, j - 1)$ 을 방문한 후 $(i, j)$ 를 방문하여 얻을 수 있는 가치의 최댓값
$r i g h t (i, j)$ : $(i, j + 1)$ 을 방문한 후 $(i, j)$ 를 방문하여 얻을 수 있는 가치의 최댓값

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

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

u p (i, j) = max [u p (i - 1, j), l e f t (i - 1, j), r i g h t (i - 1, j)] + v a l (i, j)

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

l e f t (i, j) = max [u p (i, j - 1), l e f t (i, j - 1)] + v a l (i, j)

마찬가지로 $r i g h t$ 는

r i g h t (i, j) = max [u p (i, j + 1), r i g h t (i, j + 1)] + v a l (i, j)

점화식이 나왔으니 이제 초기값을 구합시다. $r i g h t (0, j)$ 는 당연히 -INF이고, $u p (0, j)$ 는 $j = 0$ 이면 $v a l (0, 0)$ , 아니면 -INF입니다. $l e f t (0, j)$ 는 $v a l (0, 0)$ 부터 $v a l (0, j)$ 까지의 합입니다.

재귀함수와 메모이제이션으로 구현한다면 문제 없지만 반복문으로 구현할 땐 순서가 매우 중요합니다. $u p$ 을 먼저 구하고 $l e f t$ , $r i g h t$ 를 나중에 구해야 하며 $l e f t$ 는 왼쪽에서 오른쪽으로, $r i g h t$ 는 오른쪽에서 왼쪽으로 구하고 $u p$ 은 마음대로입니다.

#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;
}