[동적 계획법] 이코테 금광(Java)

📚 문제

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

 

만약 다음과 같이 3x4 크기의 금광이 존재한다고 가정한다면,

(2,1) -> (3,2) -> (3,3) -> (3,4)의 위치로 이동하면 총 19만큼의 금을 채굴할 수 있으며, 이때의 값이 최댓값이다.

 

 

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

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

둘째 줄에 nxm개의 위치에 매장된 금의 개수가 공백으로 구분되어 입력된다. (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

 

📝 문제 해결

테이블 정의

arr[][]: 초기 금광 정보를 담는 테이블

dp[][] : 최대 금의 크기를 저장하는 테이블

 

점화식 찾기

• 왼쪽 위에서 오는 경우
• 왼쪽 아래에서 오는 경우
• 왼쪽에서 오는 경우

이 3가지 경우 중에서 가장 많은 금을 가지고 있는 경우를 테이블에 저장해주면 된다.

 dp[i][j] = arr[i][j] + Math.max(dp[i-1][j-1], dp[i][j-1], dp[i+1][j-1])

 

💻 코드

package dynamicProgramming;

import java.io.*;
import java.util.*;

public class dp04 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        int[][] arr = new int[20][20];
        int[][] dp = new int[20][20];

        for (int tc = 0; tc < T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            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] + Math.max(leftUp, Math.max(leftDown, left));
                }
            }
            int max = 0;
            for (int i = 0; i < n; i++) {
                max = Math.max(max, dp[i][m - 1]);
            }
            System.out.println(max);
        }
    }
}