알고리즘 풀이 - 백준 1932(정수 삼각형, DP)

 

관련글

 

Dynamic Programming 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

 

이 문제는 삼각형의 형태로 이루어진 숫자의 배열을 위층 부터 아래층으로 합하면서 내려올 때, 가장 큰 값이 되는 경로의 결과값을 구하는 문제이다

 

 

2. 풀이

 

이 문제는 삼각형의 형태이기 때문에 위층에서 아래층으로 내려오며 선택할 수 있는 경로가 일정하다. 

아래의 그림을 보자.

 

위와 같이 배치를 한다고 하면, 위층에서 아래층으로 영향을 미치는 수는 결국 일정한 규칙을 가진다는 것을 알 수 있다.

여기서 가로 위치를 살펴보면 현재 값에 영향을 미치는 경우는 다음의 경우와 같다.

① 제일 좌측 노드의 경우 같은 가로 위치의 바로 위층의 수에만 영향을 받는다.
② 중간 노드의 경우 같은 가로 위치와 그 바로 왼쪽 위치의 위층 수에만 영향을 받는다.
③ 제일 우측 노드의 경우 왼쪽 노드의 바로 위층 수에만 영향을 받는다.

 

따라서, 이 문제는 특정한 규칙을 갖고 이전의 수에 영향을 받으며 정답을 구할 수 있는 DP로 풀 수 있는 문제이다.

여기서 State는 어떻게 될까? 현재 몇 층인지, 가로 위치가 어떻게 되는지의 2가지가 State이다. 따라서 DP[][]의 2차원 배열로 State를 저장할 수 있다.

State의 정의는 다음과 같다.
정의 : DP[N][M] = N층의 M위치의 위층 부터 값을 더해내려왔을 때의 최대값

 

점화식은 다음과 같다. 원래 숫자를 저장하는 배열을 arr배열이라고 하자.
점화식 : 
① 가장 좌측의 경우 : DP[N][0] = DP[N-1][0] + arr[N][0]
② 중간 값의 경우 : DP[N][M] = MAX(DP[N-1][M-1], DP[N-1][M]) + arr[N][M]
③ 가장 우측의 경우 : DP[N][N] = DP[N-1][N-1]

기저 상태는 어떨까? N=0 (index 기준)일 때로 가장 위 층에 위치할 경우이다.
기저 상태 : DP[0][0] = arr[0][0]

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

1) Bottom-up 방식

import java.io.*;

public class Main{
    static int[][] dp;
    static int[][] arr;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        
        dp = new int[500][500];
        arr = new int[500][500];
        
        for(int i=0; i < n; i++){
            String[] line = br.readLine().split(" ");
            
            for(int j=0; j <= i; j++){
                arr[i][j] = Integer.parseInt(line[j]);
                
                // 기저 상태
                if(i == 0){
                    dp[i][j] = arr[i][j];
                    continue;
                }
                
                // 제일 좌측의 수인 경우
                if(j == 0){
                    dp[i][j] = dp[i-1][j] + arr[i][j];
                // 제일 우측의 수인 경우
                } else if(j == i){
                    dp[i][j] = dp[i-1][j-1] + arr[i][j];
                // 그 외 중간의 경우
                } else {
                    dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + arr[i][j];
                }
            }
        }
        int result = 0;
        for(int i=0; i < n; i++){
            result = Math.max(result, dp[n-1][i]);
        }
        
        bw.write(String.valueOf(result));
        bw.flush();
        br.close();
    }
}

 

2) Top-Down 방식

import java.io.*;

public class Main{
    static int[][] dp;
    static int[][] arr;
    static int n;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        n = Integer.parseInt(br.readLine());
        
        dp = new int[500][500];
        arr = new int[500][500];
        for(int i=0; i < n; i++){
            String[] line = br.readLine().split(" ");
            
            for(int j=0; j <= i; j++){
                arr[i][j] = Integer.parseInt(line[j]);
                dp[i][j] = -1; // 삼각형 값이 0도 있을 수 있으니 -1로 초기화
            }
        }
        
        for(int i=0; i < n; i++){
            topDown(n-1, i);
        }
        
        int result = 0;
        for(int i=0; i < n; i++){
            result = Math.max(result, dp[n-1][i]);
        }
        
        bw.write(String.valueOf(result));
        bw.flush();
        br.close();
    }
    
    // Top-down 방식, 높이를 y, 밑변을 x로 표현하자
    public static int topDown(int y, int x){
        // 가장 높은 위치일 때는 기저 상태
        if(y == 0) return dp[y][x] = arr[y][x];
        
        // 가장 좌측의 수인 경우
        if(x == 0) return dp[y][x] = topDown(y-1, x) + arr[y][x];
        
        // 가장 우측의 수인 경우
        if(x == n) return dp[y][x] = topDown(y-1, x-1) + arr[y][x];
        
        // 그 외의 중간 위치의 수인 경우
        if(dp[y][x] >= 0) return dp[y][x]; // 기존의 값이 있는 경우(-1로 초기화 했으니 0이상)
        
        dp[y][x] = Math.max(topDown(y-1, x-1), topDown(y-1, x)) + arr[y][x];
        
        return dp[y][x];
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.