[이코테][Java] 금광

문제 설명

n × m 크기의 금광의 각 칸에 특정한 크기의 금이 들어있고, 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다.

- 맨 처음에는  첫 번째 열의 어느 행에서든 출발할 수 있다.

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

위의 규칙을 가지고 이동할 때, 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세요.

 

입력조건

• 첫째 줄에 테스트 케이스 T
• 매 테스트 케이스의 첫째 줄에 n과 m
• 매 테스트 케이스의 둘째 줄에 n × m개의 금의 개수

출력조건

• 테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기

입출력 예시  

입력예시	출력예시
2 3 4 1 3 3 2 2 1 4 1 0 6 4 7 4 4 1 3 1 4 2 2 4 1 5 0 2 3 0 6 1 2	19 16

 

 

 

 

문제 풀이

• 다이나믹 프로그래밍으로 풀이
• 금광의 모든 위치에 대해서, 이전 위치일 수 있는 3가지 경우(왼쪽 위에서 오는 경우, 왼쪽에서 오는 경우, 왼쪽 아래에서 오는 경우)를 구하고
• 그 중에서 가장 많은 금을 현재 위치의 금에 더한다.
• 위의 방식으로 dp 테이블을 모두 채운 후, 가장 오른쪽 열에서 금의 크기가 가장 큰 것을 구한다.
• 점화식으로 표현하면 아래와 같다.

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

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());

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

            int[][] array = new int[n][m];
            int[][] dp = new int[n][m];

            //금광 정보 입력
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    array[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            //dp 테이블 초기화
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    dp[i][j] = array[i][j];
                }
            }

            //dp 시작
            for (int j = 1; j < m; j++) {
                for (int i = 0; i < n; i++) {
                    int left_up, left_down, left;
                    //왼쪽 위 -> dp[i-1][j-1]
                    if (i == 0) {
                        left_up = 0;
                    } else {
                        left_up = dp[i - 1][j - 1];
                    }

                    //왼쪽 -> dp[i][j-1]
                    left = dp[i][j - 1];

                    //왼쪽 아래 -> dp[i+1][j-1]
                    if (i == n - 1) {
                        left_down = 0;
                    } else {
                        left_down = dp[i + 1][j - 1];
                    }
                    dp[i][j] = dp[i][j] + Math.max(left_up, Math.max(left, left_down));
                }
            }

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

 

 

  ✔️ 처음에 생각했던 idea

• 맨 처음에는 첫 번째 열에서 금이 가장 많은 행에서 출발한다.
• 이후에는 현재 위치를 기준으로 다음 위치가 될 수 있는 3가지 경우(오른쪽 위, 오른쪽, 오른쪽 아래) 중에 가장 많은 금이 위치한 곳으로 이동하면서 금의 최대값을  구한다.
• 하지만 이 풀이는 다음과 같은 반례가 존재한다.
  • 위의 내용을 따르면 주황색처럼 이동해서 금의 크기는 13이 된다.
  • 하지만 여기서 얻을 수 있는 금의 최대 크기는 파란색처럼 이동해서 17이다. 

    

---

[참고서적]

이것이 취업을 위한 코딩 테스트다 with 파이썬 by 나동빈