[BOJ-11048]이동하기

[문제설명]

N x M 크기 맵이 있고, 1 x 1 크기에는 수가 적혀있다.

[1, 1]에서 이동하는 방법은 3가지다.

1. [Row + 1, Col]
2. [Row, Col + 1]
3. [Row + 1 , Col + 1]
   

[1, 1] 에서 [N, M]까지 각 칸의 수를 더하고 이동하며 [N,M]까지 도달 시 가장 커지는 경우 그 값을 출력한다.

[문제풀이]

이전에 이동하여 값을 가진 한 3칸 중에 그 위치값이 더 크면 갱신시킨다. 총 3가지 경우이다. 

1. [Row - 1 ][Col]
2. [Row][Col - 1]
3. [Row - 1][Col - 1]

이동하는 3방향이 우측아래쪽으로 가는 경우만 존재하므로 되돌아 올라가는 경우는 없기에 간단하게 코드를 작성할 수 있다.

현재 값을 구할 위치가 dp[R][C] 라 가정하자.

dp[R][C] = max(dp[R-1][C], dp[R][C-1], dp[R-1][C-1]) + input[R][C]

위 식을 2중 for lo dp 테이블을 완성한다. 

그리고 dp[N][M] 의 값을 출력하면 된다. 

[C++ Source Code]

#include<iostream>
const int M = 1010;
int dp[M][M];
int im[M][M];
int RO, CO;
 
// 3개중 하나. 
// 자기자신 더하기 그위치 값이 더 크면 갱신, 
// 하지만 자기자신의 값이 최대값임을 보장시켜줘야함.
int m_max(int a, int b, int c) {
    int ret = (a > b) ? a : b;
    ret = (ret > c) ? ret : c;
    return ret;
}
 
int main() {
    //freopen("input.txt", "r", stdin);
    scanf("%d %d", &RO, &CO);
    for (register int r = 1; r <= RO; ++r) {
        for (register int c = 1; c <= CO; ++c) {
            scanf("%d", &im[r][c]);
            dp[r][c] = m_max(dp[r - 1][c - 1], dp[r - 1][c], dp[r][c - 1]);
            dp[r][c] += im[r][c];
        }
    }
 
    printf("%d\n", dp[RO][CO]);
    return 0;
}