문제
n x m 크기의 금광이 있습니다. 금광은 1 x 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있습니다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있습니다. 이후에 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세요.
만약 다음과 같이 3 x 4 크기의 금광이 존재한다고 가정합시다.
| 1 | 3 | 3 | 2 |
| 2 | 1 | 4 | 1 |
| 0 | 6 | 4 | 7 |
가장 왼쪽 위의 위치를 (1, 1), 가장 오른쪽 아래의 위치를 (n, m)이라고 할 때, 위 예시에서는 (2, 1) -> (3, 2) -> (3, 3) -> (3, 4)의 위치로 이동하면 총 19만큼의 금을 채굴할 수 있으며, 이때의 값이 최댓값입니다.
입력
- 첫째 줄에 테스트 케이스 T가 입력됩니다. (1 ≤ T ≤ 1000)
- 매 테스트 케이스 첫째 줄에 n과 m이 공백으로 구분되어 입력됩니다. (1 ≤ n, m ≤ 20)
둘째 줄에 n x m개의 위치에 매장된 금의 개수가 공백으로 구분되어 입력됩니다.
(1 ≤ 각 위치에 매장된 금의 개수 ≤ 100)
출력
- 테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기를 출력합니다.
- 각 테스트 케이스는 줄 바꿈을 이용해 구분합니다.
입출력 예시
2
3 4
1 3 3 2 2 1 4 1 0 6 4 7
4 4
1 3 1 5 2 2 4 1 5 0 2 3 0 6 1 2
19
16
소스 코드
/*
1. 왼쪽 위에서 오는 경우
2. 왼쪽 아래에서 오는 경우
3. 왼쪽에서 오는 경우
dp[i][j] = array[i][j] + max(dp[i - 1][j - 1], dp[i][j - 1], dp[i + 1][i - 1])
*/
const T = 2;
const input = [
[3, 4],
[1, 3, 3, 2, 2, 1, 4, 1, 0, 6, 4, 7],
[4, 4],
[1, 3, 1, 5, 2, 2, 4, 1, 5, 0, 2, 3, 0, 6, 1, 2]
];
for (let t = 0; t < T; t++) {
const N = input[0][0];
const M = input.shift()[1];
const dp = [];
let index = 0;
for (let d = 0; d < N; d++) {
dp.push(input[0].slice(index, index + M));
index += M;
}
input.shift();
for (let j = 1; j < M; j++) {
for (let i = 0; i < N; i++) {
let leftUp = 0, leftDown = 0;
if (i !== 0) {
leftUp = dp[i-1][j-1];
}
if (i !== N - 1) {
leftDown = dp[i+1][j-1];
}
const left = dp[i][j-1];
dp[i][j] = dp[i][j] + Math.max(leftUp, leftDown, left);
}
}
let result = 0;
for (let i = 0; i < N; i++) {
result = Math.max(result, dp[i][M - 1]);
}
console.log(result);
}느낀 점
아직 혼자 힘으로 해결할 수는 없을 것 같다. 다이나믹 프로그래밍이 어떻게 실제 기출문제에 적용이 되는지 느낌과 코드 스타일만 익히고 나중에 다시 풀어봐야 할 것 같다.
(｡･∀･)ﾉﾞ