[S1] 백준 1932 정수 삼각형 - Java

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

동적 계획법으로 푸는 문제이다.

좀 더 까다로운 2차원 배열의 문제이다.

왼쪽이 arr 배열, 오른쪽이 dp 배열이다. 위처럼 n층의 입력된 숫자를 2차원 배열로 만들고, 더 누적합이 높은 경우의 수를 차례로 찾아가며 dp 배열을 채워주면 된다.

 

[풀이]

import java.util.Scanner;

public class N_1932 {
    static int n;
    static int arr[][];
    static int dp[][];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); // 삼각형의 크기

        // 2차원 배열 생성
        arr = new int[n][n];
        int end = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < end; j++) {
                arr[i][j] = sc.nextInt();
            }
            end++;
        }
//        System.out.println(Arrays.deepToString(arr));
        dp = new int[n][n];
        dp[0][0] = arr[0][0];
        triangle(1, 2);
//        System.out.println(Arrays.deepToString(dp));
        int max = dp[n-1][0];
        for (int i = 1; i < n; i++) {
            if (dp[n-1][i] > max) {
                max = dp[n-1][i];
            }
        }
        System.out.println(max);
    }
    static int triangle(int idx, int end) {
        if (idx == n) {
            return 1;
        }
        for (int i = 0; i < end; i++) {
            if (i == 0) {
                dp[idx][0] = dp[idx - 1][0] + arr[idx][0];
            } else {
                dp[idx][i] = Math.max(dp[idx-1][i], dp[idx-1][i-1]) + arr[idx][i];
            }
        }
        return triangle(idx+1, end+1);
    }
}

먼저 각 층별 데이터를 저장하기 위해 2차원 배열을 사용해야 한다.

나는 여기서 bottom-top 방식을 사용했다. 삼각형에서 맨 꼭대기인 arr[0][0] 배열을 기준으로 아래로 내려간다.

여기서 점화식은 dp[idx][i] = Math.max(dp[idx-1][i], dp[idx-1][i-1]) + arr[idx][i] 이 해당된다.

위에서 두 번째 층일 경우(idx 값이 1일 경우)에는 꼭대기에 [0][0] 값 하나 밖에 없기 때문에 i-1를 사용하면 인덱스 참조 에러가 난다. 따라서 i == 0일 경우에만 따로 식을 세워주었다.

 

그렇게 triangle 함수의 실행이 끝나면 dp[n-1]에서 최대값을 찾으면 된다.

동적 계획법 문제에 익숙해지니 점화식을 찾는 과정만 쉽게 넘어가면 풀이 하는데 노하우가 생겼다!

다이나믹 프로그래밍은 결국 점화식 + 메모이제이션의 과정이기 때문에 해당 부분을 알고 있으면 될 것 같다.