[BOJ 백준] 정수 삼각형(1932) Java

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

 

문제 설명 : 

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

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

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

 

입력 : 

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

 

출력 : 

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

 

예제 입력 : 

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

 

예제 출력 : 

30

 

 

접근법 : 

1) 어떻게 풀 것인가?

문제의 정수 삼각형을 코드로 작성하기위해 n*n의 정사각형 모양 행렬로 만들고,

조건에 따라 그림을 그려보면 아래와 같은 그림이 나온다.

각 화살표는 아래층으로 내려갈 수 있는 모든 경우의 수이고, 

화살표를 받는 입장에서는 받는 값들 중 큰 값을 받으면 된다.

 

즉, 첫번째 줄부터 시작해서 가능한 모든 경우의 수의 최댓값을 

메모해나가면 (Memoization - DP) 자연스레 마지막 N번째 줄에서 최댓값을 구할 수 있다.

 

코드로 구현할때는 크게 2단계로 구현하면 된다.

 

* int[ ] = dp[i][j] 는 i 행 j열의 가능한 최댓값

 

① 아랫칸 값들과 값을 비교하는 과정은 아래와 같이 표현 가능하다.

             dp[i+1][j] = Math.max(dp[i+1][j], dp[i][j]);          // 바로 밑(↓)에 칸과 비교
             dp[i+1][j+1] = Math.max(dp[i+1][j+1], dp[i][j]);   // 우측 대각선 아래(↘) 칸과 비교

 

② 한 줄이 끝나면 모든 줄에 해당 칸에서 얻을 수 있는 점수를 더해주는 과정

           for (int j=1; j<=i+1; j++){
             dp[i+1][j] += map[i+1][j]; 
            }

 

합치면 DP가 구현되는 곳의 코드는 아래와 같다.

 

   // 2. 1 ~ (N-1) Row에서 뿌려주는 DP 실행
        dp[1][1] = map[1][1];
        for (int i=1; i<=N-1; i++){
            for (int j=1; j<=i; j++){
            	// 가능한 최댓값으로 갱신
            	dp[i+1][j] = Math.max(dp[i+1][j], dp[i][j]);
            	dp[i+1][j+1] = Math.max(dp[i+1][j+1], dp[i][j]);
            }
            for (int j=1; j<=i+1; j++){
            	dp[i+1][j] += map[i+1][j]; 
            }
        }

 

기본적인 DP(Dynamic Programming), 동적계획법 문제로 전체 구현은 아래 Java 코드 참조.

 

2) 시간복잡도

1~N까지의 합이므로 N*(N-1)/2. 크게 잡아도 O(N^2), N은 500으로 넉넉함.

(Java 기준 280ms)

 

3) 공간복잡도

n이 500으로 500^2을 해도 int 배열로 넉넉함.

 

4) 풀면서 놓쳤던점

문제를 대충 읽고 삼각형의 뿌려지는 범위를 2칸이 아닌 3칸으로 더 넓게 해석함.

 

5) 이 문제를 통해 얻어갈 것

DP의 기본적 활용.

 

Java 코드 :

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

// 백준 1932
public class Main {
    
    static int N, ans;
    static int [][] map, dp;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        map = new int[N+1][N+1];
        dp = new int[N+1][N+1];
        
        // 1. 입력
        for (int i=1; i<=N;i++){
        	st = new StringTokenizer(br.readLine());
            for (int j=1; j<=i; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 2. 1 ~ (N-1) Row에서 뿌려주는 DP 실행
        dp[1][1] = map[1][1];
        for (int i=1; i<=N-1; i++){
            for (int j=1; j<=i; j++){
            	// 가능한 최댓값으로 갱신
            	dp[i+1][j] = Math.max(dp[i+1][j], dp[i][j]);
            	dp[i+1][j+1] = Math.max(dp[i+1][j+1], dp[i][j]);
            }
            for (int j=1; j<=i+1; j++){
            	dp[i+1][j] += map[i+1][j]; 
            }
        }
        
        // 3. 마지막 줄에서 가장 큰 값 찾아서 출력
        for (int j=1; j<= N; j++){
            ans = Math.max(ans, dp[N][j]);
        }
        bw.write(String.valueOf(ans));
        
        bw.flush();
        bw.close();
        br.close();
    }

}