195. 금광

• n × m 크기의 금광이 있다. 금광은 1 × 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있다.

• 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작한다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있다.

• 이후에 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 한다.

• 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하라

3 x 4 크기의 금광이 존재한다고 가정

가장 왼쪽의 위치를 (1, 1), 가장 오른쪽 아래의 위치를 (n, m)이라고 할 때, 위 예시에서는 (2, 1) -> (3, 2) -> (3,3) -> (3, 4)의 위치로 이동하면 총 19만ㅋ믐의 금을 채굴할 수 있으며, 이때의 값이 최댓값이다.

• 입력조건

  • 첫째 줄에 테스트 케이스 T가 입력됩니다. (1 ≤ T ≤ 100)

  • 매 테스트 케이스 첫째 줄에 n과 m이 공백으로 구분되어 입력됩니다. (1 ≤ n, m ≤ 20)

  • 둘째 줄에 n x m개의 위치에 매장된 금의 개수가 공백으로 구분되어 입력됩니다. (0 ≤ 각 위치에 매장된 금의 개수 ≤ 100)

• 출력조건

  • 테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기를 출력합니다.

    • 각 테스트 케이스는 줄 바꿈을 이용해 구분합니다.

1. 다이나믹 프로그래밍

for tc in range(int(input())):
  n, m = map(int,input().split())
  array = list(map(int, input().split()))

  dp = []
  index = 0
  for i in range(n):
    dp.append(array[index: index + m])
    index += m

  for j in range(1, m):
      for i in range(n):
        #왼쪽 위에서 오는 경우
        if i == 0:
          left_up = 0
        else:
          left_up = dp[i - 1][j - 1] 
        #왼쪽 아래에서 오는 경우
        if i == n - 1:
          left_down = 0
        else:
          left_down = dp[i + 1][j - 1]
        #왼쪽에서 오는 경우
        left = dp[i][j - 1]
        dp[i][j] = dp[i][j] + max(left_up, left_down, left)

  result = 0

  for i in range(n):
    result = max(result, dp[i][m - 1])

  print(result)

2. C++

#include <bits/stdc++.h>

using namespace std;

int testCase, n, m;
int arr[20][20];
int dp[20][20];

int main(void) {
    // 테스트 케이스(Test Case) 입력
    cin >> testCase;
    for (int tc = 0; tc < testCase; tc++) {
        // 금광 정보 입력
        cin >> n >> m;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> arr[i][j];
            }
        }
        // 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dp[i][j] = arr[i][j];
            }
        }
        // 다이나믹 프로그래밍 진행
        for (int j = 1; j < m; j++) {
            for (int i = 0; i < n; i++) {
                int leftUp, leftDown, left;
                // 왼쪽 위에서 오는 경우
                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];
                // 왼쪽에서 오는 경우
                left = dp[i][j - 1];
                dp[i][j] = dp[i][j] + max(leftUp, max(leftDown, left));
            }
        }
        int result = 0;
        for (int i = 0; i < n; i++) {
            result = max(result, dp[i][m - 1]);
        }
        cout << result << '\n';
    }
}