[이코테] C++ 금광 - DP

문제

• n x m 크기의 금광이 있습니다. 금광은 1 x 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있습니다.
• 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있습니다.
• 이후에 m - 1번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다.
• 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세요.

입력 조건

• 첫째 줄에 테스트 케이스 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. 처음 행에서 각 값이 가는 곳의 최대값을 구해야 한다.

[0][0] [0][1] [0][2] [0][3]
[1][0] [1][1] [1][2] [1][3]
[2][0] [2][1] [2][2] [2][3]
[3][0] [3][1] [3][2] [3][3]

[0][0]은 [0][1], [1][1]을 갈 수 있다.
[1][0]은 [0][1], [1][1], [2][1]을 갈 수 있다.
이런식으로 첫번째 행 4개의 값들이 가는 곳을 둘러봐야한다.

풀이

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

int T, test_case, n, m, maxNum, leftUp, justLeft, leftDown;
int dp[20][20];

int main() {
	cin >> T;

	for (test_case = 0; test_case < T; test_case++) {

		cin >> n >> m;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cin >> dp[i][j];
			}
		}

		for (int j = 1; j < m; j++) {
			for (int i = 0; i < n; i++) {
				// 왼쪽 위에서 오는 경우
				if (i == 0) leftUp = 0;
				else leftUp = dp[i - 1][j - 1];

				// 왼쪽 아래서 오는 경우
				if (i == n - 1) leftDown = 0;
				else leftDown = dp[i + 1][j - 1];

				// 그냥 왼쪽
				justLeft = dp[i][j - 1];
				dp[i][j] += max(leftUp, max(justLeft, leftDown));
			}
		}
		int result = 0;
		for (int i = 0; i < n; i++) {
			result = max(result, dp[i][m - 1]);
		}

		cout << result << "\n";
	}
}