[JAVA] 백준 #1932 정수 삼각형 | Dynamic Programming | DFS 시간 초과 해결 방법 | 예외 처리 구현

 

[JAVA] 백준 #1932 정수 삼각형

https://www.acmicpc.net/problem/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번째 줄까지 정수 삼각형이 주어진다.

 

🖥️ 출력

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

 

---

🔎  풀이

처음에 문제를 풀 때는 dfs를 사용해서 재귀함수로 리프노드에 도달하면 최댓값을 찾는 로직으로 다음과 같이 구성했다.

 

🔹 DFS 시간 초과

   public static void dfs( int index, int jump, int sum ){
   
        if( index > tree.length - 1 ){ // 리프 노드 도달
            MAX = Math.max(MAX, sum);
            return;
        }

        SumTree[index] = tree[index] + Math.max( SumTree[index + jump], SumTree[index + jump + 1]  );
        sum += tree[index];
        dfs( index + jump, jump + 1, sum );
        dfs( index + jump + 1, jump + 1, sum);
        
    }

하지만 일일이 모든 구간을 찾아 탐색하는 dfs는 시간초과가 발생하므로 다른 최적화된 알고리즘을 찾아야 했다.

주어진 알고리즘 분류가 '다이나믹 프로그래밍'이길래 다이나믹 프로그래밍의 로직으로 코드를 바꿔야 했다.

 

다이나믹 프로그래밍을 구현할 때는 그래프를 직접 그려보는 것이 훨씬 이해가 잘된다. 그래서 다음과 같이 그래프를 그리고, 인덱스의 규칙을 찾아보았다. 아래 그림에서 노드에 담긴 값은 트리를 배열에 저장했을 때 배열에서의 인덱스를 의미한다. 

 

주어진 예제에 대해 그래프를 그리면 다음과 같다. 부모, 자식 노드 간의 인덱스 규칙성은 그래프를 보면 쉽게 찾을 수 있다. 

부모 인덱스에 부모의 노드 레벨을 더하면 왼쪽 자식 노드의 인덱스가 나오고, 거기에 1을 더하면 오른쪽 자식 노드의 인덱스가 나온다.

그럼 우리는 맨 아래 리프노드부터 시작해서 위로 올라가면서 두 개의 자식 노드 중 큰 값을 가진 노드의 값과 본인의 가중치 값을 더해나가면, 마지막 루트 노드에 도달했을 때는 루트 노드에 최댓값이 담겨있을 것이다. 

 

그럼 이 로직으로 dp를 구현하기 위해서는 입력받은 가중치를 저장하는 Tree배열과 리프노트부터 아래에서 위로 합을 갱신해 나가며 노드에 최댓값을 저장하는 배열 SumTree가 필요하다. 그리고 두 배열의 크기는 첫 항이 1이고, 공차가 1일 때 주어진 레벨 n까지의 합 공식을 사용하면 된다. 다만 우리는 인덱스 0을 사용하지 않고 1부터 공차의 합인 'n(n+1)/2'까지의 인덱스가 필요하므로 +1을 해준다.

 

🔹 DP 구현부

    public static void dp( ){

        // 리프노드 채우기
        int cnt = N;
        for( int i = tree.length - 1 ; ; i-- ){
            if( cnt == 0 ) break;
            SumTree[i] = tree[i];
            cnt--;
        }

        int level = N - 1;
        int count = level;

        for( int i = tree.length - 1 - N ; i > 0 ; i-- ){
            if( count == 0 ) {
                level --;
                count = level;
            }
            SumTree[i] = tree[i] + Math.max( SumTree[ i + level ], SumTree[ i + level + 1 ] );
            count--;
            
        }
    }

dp는 다음과 같이 구현했다. 우선 맨 처음에는 SumTree 배열에서 자식 노드가 없는 '리프 노드'를 채워준다. 로직이 현재 노드를 갱신할 때 자식 노드 값을 탐색해 갱신하므로 자식 노드가 없는 리프 노드는 본인의 가중치를 가져와서 그대로 저장하면 된다.

그다음엔 본격적인 dp를 하면 되는데, 여기서 자식 노드의 인덱스는 부모 노드의 인덱스에 부모의 레벨을 더하면 나온다는 것을 우리는 알고 있다. 그런데 for문을 통해서 탐색할 때, 이 레벨이 변경되는 것을 어떻게 알고 자식 인덱스를 찾아갈 수 있을까?

여기서 우리가 또 찾을 수 있는 특징이 n레벨에는 n개의 노드가 있다는 것이다. 그러니까 for문을 돌면서 n레벨의 n개의 노드를 모두 탐색했다면 레벨을 n-1로 갱신해서 다음 레벨을 탐색하면 된다. 

🔹 전체 코드

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N;
    static int[] tree;
    static int[] SumTree;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bf.readLine());
        tree = new int[ N*(N+1)/2 + 1 ];
        SumTree = new int[ N*(N+1)/2 + 1 ];

        for( int i = 1; i < N*(N+1)/2 + 1; ){
            StringTokenizer line = new StringTokenizer(bf.readLine(), " ");
            while(line.hasMoreTokens()){
                tree[i] = Integer.parseInt(line.nextToken());
                i++;
            }
        }

        dp();

        System.out.println(SumTree[1]);

    }// end of main

    public static void dp( ){

        // 리프노드 채우기
        int cnt = N;
        for( int i = tree.length - 1 ; ; i-- ){
            if( cnt == 0 ) break;
            SumTree[i] = tree[i];
            cnt--;
        }

        int level = N - 1;
        int count = level;

        for( int i = tree.length - 1 - N ; i > 0 ; i-- ){
            if( count == 0 ) {
                level --;
                count = level;
            }
            SumTree[i] = tree[i] + Math.max( SumTree[ i + level ], SumTree[ i + level + 1 ] );
            count--;
            
        }
    }// end of dp

}// end of class

 

 

🍀 유사한 문제