DP - 금광

문제

이것이 취업을 위한 코딩테스트다 with 파이썬 (https://youtu.be/5Lu34WIx2Us)

• 금광의 크기는 N x M, 금광은 1 x 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있다.
• 채굴자는 첫번째 열의 어느 행에서든 출발할 수 있다.
• 이후 m-1 번에 걸쳐 매번 오른쪽 위 / 오른쪽 / 오른쪽 아래 3가지 중 하나의 위치로 이동 가능하다.
• 채굴자가 얻을 수 있는 금의 최대 크기를 출력하라.

 

입력 조건

• 첫번째 줄에 테스트 케이스 개수 T가 입력 (1 <= T <= 1000)
• 매 테스트케이스 첫째 줄에 N M이 공백으로 구분되어 입력 (1 <= n, m <= 20)
  둘째 줄에 n x m개의 위치에 매장된 금의 개수가 공백으로 구분되어 입력 (1 <= 금 개수 <= 100)

 

출력 조건

• 테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기를 줄바꿈으로 구분하여 출력

 

풀이

• 각 칸까지의 최적의 해 (얻을 수 있는 금의 최댓값)
  = 현재 칸에 있는 금의 개수 + (왼쪽 위, 왼쪽, 왼쪽 아래 각 칸까지의 최적의 해 중 최댓값)

• 점화식
  

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

• 첫번째 행, 마지막 행은 왼쪽에서 2개의 칸만 참고, 나머지 행은 왼쪽에서 3개의 칸을 참고
• 첫번째 열 칸들의 최적의 해는 자기자신이 가지고 있는 금의 개수이기 때문에 별도로 계산 필요X
• DP 테이블을 갱신하는 반복문에서 각 칸에 접근하는 순서에 주의한다.
  문제에서 금광에 접근하는 방향이 좌→우 이므로, 열 → 행 순으로 접근해야 한다.
  행 → 열 순으로 접근하는 경우 아직 최적의 해가 계산되지 않은 칸의 값을 이용해서 새로운 칸의 최적의 해를 구하려 시도하기 때문에 제대로된 결과가 나오지 않는다.

 

코드

import java.util.Scanner;

// 금광 문제
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int testCase = sc.nextInt();
        StringBuffer sb = new StringBuffer();

        // 테스트 케이스 별 진행
        for (int tc = 0; tc < testCase; tc++) {
            int n = sc.nextInt();
            int m = sc.nextInt();

            // 각 칸에 존재하는 금의 양 입력받기
            int[][] dp = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    dp[i][j] = sc.nextInt();
                }
            }

            // DP Bottom-Up
            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(left, leftDown));
                }
            }

            // 마지막 열의 칸 중 최대값 구하기
            int result = 0;
            for (int i = 0; i < n; i++) {
                result = Math.max(result, dp[i][m - 1]);
            }

            // 얻을 수 있는 금의 최대 개수 저장
            sb.append(result + "\n");
        }
        System.out.println(sb);
    }
}

 

DP 부분을 3가지 경우(첫번째 행일 경우 / 마지막 행일 경우 / 그 외 경우)에 따라 풀어쓰면 아래와 같다.

import java.util.Scanner;

// 금광 문제
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int testCase = sc.nextInt();
        StringBuffer sb = new StringBuffer();

        // 테스트 케이스 별 진행
        for (int tc = 0; tc < testCase; tc++) {
            int n = sc.nextInt();
            int m = sc.nextInt();

            // 각 칸에 존재하는 금의 양 입력받기
            int[][] dp = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    dp[i][j] = sc.nextInt();
                }
            }

            // DP Bottom-Up
            for (int j = 1; j < m; j++) {
                for(int i = 0; i < n; i++){
                    // 각 칸까지의 최적의 해 (얻을 수 있는 금의 최대 개수)
                    if (i == 0) {
                        dp[i][j] = dp[i][j] + Math.max(dp[i][j - 1], dp[i + 1][j - 1]);
                    } else if (i == n - 1) {
                        dp[i][j] = dp[i][j] + Math.max(dp[i - 1][j - 1], dp[i][j - 1]);
                    } else{
                        dp[i][j] = dp[i][j] + Math.max(dp[i - 1][j - 1], Math.max(dp[i][j - 1], dp[i + 1][j - 1]));
                    }
                }
            }

            int result = 0;
            for (int i = 0; i < n; i++) {
                result = Math.max(result, dp[i][m-1]);
            }

            // 얻을 수 있는 금의 최대 개수 저장
            sb.append(result + "\n");
        }
        System.out.println(sb);
    }
}