31.금광

📍 문제 설명

[문제]

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

 

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

 

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

 

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

 

[입력 조건]

1. 첫째 줄에 테스트 케이스 T가 입력됩니다. (1 <= T <= 1000)

 

2. 매 테스트 케이스 첫째 줄에 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

 

💡 접근

채굴한 금의 크기를 저장해놓는 dp 테이블을 이용하여 각 지점에서 왼쪽위 왼쪽아래 왼쪽에서 오는 경우를 판단하여 값을 저장한다.

 

👩‍💻 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        int t = kb.nextInt();
        for(int tc = 0; tc < t; tc++) {
            int n = kb.nextInt();
            int m = kb.nextInt();
            int[][] arr = new int[20][20];
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    arr[i][j] = kb.nextInt();
                }
            }

            int[][] dp = new int[20][20];
            //채굴한 금을 저장해놓는 dp 테이블 초기화
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    dp[i][j] = arr[i][j];
                }
            }

            //1열부터 시작
            for(int j = 1; j < m; j++) {
                //모든 행에 대해서 기록해나간다.
                for(int i = 0; i < n; i++) {
                    int leftUp, leftDown, left;
                    //왼쪽 위에서 오는 경우
                    //i = 0이면 해당 지점에 왼쪽 위에서 올 수 없으니 0
                    if(i == 0) leftUp = 0;
                    else leftUp = dp[i - 1][j - 1];
                    //왼쪽 아래에서 오는 경우
                    //i == n - 1이면 해당 지점에 왼쪽 아래에서 올 수 없으니 0
                    if(i == n - 1) leftDown = 0;
                    else leftDown = dp[i + 1][j - 1];
                    //왼쪽에서 오는 경우
                    //세 방향 모두 올 수 있음
                    left = dp[i][j - 1];
                    dp[i][j] = dp[i][j] + Math.max(leftUp, Math.max(leftDown, left));
                }
            }
            int result = 0;
            //마지막 열의 값들 중 최댓값이 금의 최대 크기
            for(int i = 0; i < n; i++) {
                result = Math.max(result, dp[i][m - 1]);
            }
            System.out.println(result);
        }
    }
}