알고리즘 :: 이것이 코딩 테스트다 :: DP :: Q31 :: 금광

문제

n X m 크기의 금광에서 채굴자는 첫 번쨰 열부터 출발해서 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동한다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하시오.

문제접근

• 3가지 이동방법을 각각 수행한 뒤 그 결과를 메모이제이션 한다.
  • 오른쪽 위 이동: (y, x) -> (y - 1, x + 1)
  • 오른쪽 이동: (y, x) -> (y, x + 1)
  • 오른쪽 아래 이동: (y, x) -> (y + 1, x + 1)
• 모든 출발 후보 지점으로부터 DP를 수행한다.

코드

#include <iostream>
#include <cstring>
using namespace std;

static int T, N, M, mine[20][20], memo[20][20];

int solve(int y, int x) {
    if (y < 0 || y >= N || x < 0 || x >= M) return 0;	// [기저]: 범위 초과
    if (memo[y][x] != 0) return memo[y][x];	// [기저]: 이미 메모이제이션 된 값.
	
    return memo[y][x] = mine[y][x] + max(max(solve(y - 1, x + 1), solve(y, x + 1)), solve(y + 1, x + 1));
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> T;
    while (T--) {
        memset(mine, 0, sizeof(mine));
        memset(memo, 0, sizeof(memo));
        cin >> N >> M;
        for (int y = 0; y < N; ++y)
            for (int x = 0; x < M; ++x)
                cin >> mine[y][x];
        
        int answer = 0;	// 모든 출발 지점으로부터 DP를 수행 후 최대값을 찾는다.
        for (int i = 0; i < N; ++i) answer = max(answer, solve(i, 0));
        cout << answer << '\n';
    }
}