문제
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;
for (int i = 0; i < N; ++i) answer = max(answer, solve(i, 0));
cout << answer << '\n';
}
}