[백준1932] 정수 삼각형 / Java

문제주소 :www.acmicpc.net/problem/1932

1932번: 정수 삼각형

---

<문제 설명>

문제

7 3 8 8 1 0 2 7 4 4 4 5 2 6 5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

예제 입력 1

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

예제 출력 1

30

 

<풀이법>

▒ 한줄 개념: 동적 계획법(DP) ▒ 

동적 계획법에는 두 가지 방식이 있습니다.

위에서 내려오는 Top-Down 방식과, 아래에서 올라가는 Bottom-Up 방식이 그것입니다.

 

이번 문제는 Top-Down 방식을 사용하여 풀었습니다.

즉, "root부터 내려오면서, 오른쪽 자식과 왼쪽 자식 중 큰 연산값을 찾아 더해준다!" 라는 것이 핵심 개념이 되겠습니다.

식으로 나타내면 다음과 같습니다.

dp[현재 층][n 번째] = max(dp[아랫층][n 번째], dp[아랫층][n+1 번째]) + 현재 위치의 값

= dp[depth][n] = max(dp[depth+1][n], dp[depth+1][n+1]) + tree[depth][n]

 

다만, 여기서 주의할 점이 있습니다.

1. 오른쪽 자식은 없고 왼쪽 자식만 있을 경우에 대한 예외처리가 필요합니다.

2. dp의 초기화 값은 -1로 해야합니다. 0 값은 유효한 값으로서 입력 될 수 있습니다.

 

 

<코드(Java)>

package Baekjoon;

import java.util.Scanner;

public class Integer_Triangle_1932 {
    static int[][] dp;
    static int[][] tree;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int depth = sc.nextInt();
        tree = new int[depth][];
        dp = new int[depth][];
        for(int i = 0 ; i < depth; i++){
            tree[i] = new int[i+1];
            dp[i] = new int[i+1];
            for(int j = 0 ; j <= i; j++){
                tree[i][j] = sc.nextInt();
                if(i == depth-1)
                    dp[i][j] = tree[i][j];
                else
                    dp[i][j] = -1;
            }
        }

        System.out.println(find_max(0,0));
    }

    static int find_max(int n, int depth){
        if(dp[depth][n] == -1){
            if(tree[depth+1].length > n+1){
                if(tree[depth+1].length > n){
                    dp[depth][n] = max(find_max(n, depth+1), find_max(n+1, depth+1)) + tree[depth][n];
                }
                else
                    dp[depth][n] = find_max(n,depth+1) + tree[depth][n];
            }
        }
        return dp[depth][n];
    }

    static int max(int a, int b){
        return a > b ? a : b;
    }
}

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest