[Algorithm] 금광

문제

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

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

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

결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하시오.

 

풀이

n x m 크기의 배열을 새로 생성한다.

해당 배열 (i, j)에서는 현재까지 가져갈 수 있는 최대의 금을 저장하도록 한다.

 

먼저, 0열의 값들을 초기화 한다. (각 자리의 값이 최대이기 때문)

그리고 1열부터는 직전 열의 왼쪽, 왼쪽 위, 왼쪽 아래의 값과 해당 칸의 합이 가장 큰 값을 저장하도록 한다.

 

마지막 m-1열에 저장된 값들을 비교해 최대값을 출력한다.

 

import java.util.*;

public class Main {

    public static int t;
    public static int n, m;

    // 왼쪽 위, 왼쪽, 왼쪽 아래
    public static int[] dx = {-1, 0, 1};

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        t = sc.nextInt();

        int[] results = new int[t];
        
        // 테스트 케이스 
        for (int test = 0; test < t; test++) {
            
            n = sc.nextInt();
            m = sc.nextInt();

            int[][] graph = new int[n][m];

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    graph[i][j] = sc.nextInt();
                }
            }

            // 각 칸의 값은 현재까지 가져갈 수 있는 최대
            int[][] d = new int[n][m];
            for (int i = 0; i < n; i++) {
                d[i][0] = graph[i][0];
            }

            for (int j = 1; j < m; j++) {
                for (int i = 0; i < n; i++) {
                    for (int k = 0; k < 3; k++) {
                        int nx = i + dx[k];
                        // 값이 배열을 벗어나지 않아야
                        if (0 <= nx && nx < n) {
                            // 최대값을 저장
                            d[i][j] = Math.max(d[i][j], d[nx][j-1] + graph[i][j]);
                        }
                    }
                }
            }

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

            results[test] = result;
        }
        
        for (int i = 0; i < results.length; i++) {
            System.out.println(results[i]);
        }
    }
        
}