백준 1932 정수 삼각형 - JAVA

1932 문제 링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

< Top-down 방식 >

import java.io.*;
import java.util.*;
 
public class Main {
    static int[][] arr;
    static Integer[][] 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));
        
        int input = Integer.parseInt(br.readLine());
        arr = new int[input][input];
        dp = new Integer[input][input];
        
        StringTokenizer st;
        for(int i = 0; i < input; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j <= i; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());  
            }
        }
        dp[0][0] = arr[0][0];
 
        int max = 0;
        for (int i = 0; i < input; i++) {
            int value = findMax(input - 1,i);
            if(max < value) {
                max = value;
            }
        }
        bw.write(String.valueOf(max));
        bw.flush();
    }
    
    private static int findMax(int row, int col) {
        if (dp[row][col] == null) {
            if (col == 0) {
                dp[row][col] = findMax(row-1, col) + arr[row][col];
            } 
            else if (row == col) {
                dp[row][col] = findMax(row-1, col-1) + arr[row][col];
            } else {
                dp[row][col] = Math.max(findMax(row-1, col-1), findMax(row-1, col))   + arr[row][col];
            }
            
        }
        return dp[row][col];
    }
}

 
 

< Bottom-up 방식 >

import java.io.*;
import java.util.*;
 
public class Main {
    static int[][] arr;
    static int[][] 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));
        
        int input = Integer.parseInt(br.readLine());
        arr = new int[input][input];
        dp = new int[input][input];
        
        StringTokenizer st;
        for(int i = 0; i < input; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j <= i; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());    
            }
        }
        bw.write(String.valueOf(findMax(input)));
        bw.flush();
    }
    
    private static int findMax(int input) {
        dp[0][0] = arr[0][0];
        for (int i = 1; i < input; i++) {
            for (int j = 0; j <= i; j++) {
                if(j == 0) {
                    dp[i][0] = dp[i-1][0] + arr[i][0];
                }
                else if(j == i) {
                    dp[i][i] = dp[i-1][i-1] + arr[i][i];
                    
                } else {
                    dp[i][j] = arr[i][j] + Math.max(dp[i-1][j-1], dp[i-1][j]);
                }
            }  
        }
        int max = Arrays.stream(dp[input - 1]).max().getAsInt();
        return max;
    }
}

 

알고리즘 설명

---

이번 동적 계획법 문제는 탑다운방식과 바텀업 방식 모두 사용해서 해결해봤습니다. 탑다운 방식은 재귀호출스택을 사용하여 문제를 해결하는 방식이고, 바텀업 방식은 반복문을 활용하여 문제를 해결하는 방식입니다.
 
탑다운 방식은 dp[][] 배열을 생성하여, dp[i][j]의 값이 null이라면, 재귀함수 호출을 사용하여 구한값을 arr[i][j]의 값과 누적합하여, dp[][] 배열에 입히는 방식으로 진행하였고, 탑다운 방식은 반복문을 사용하여, 두 번째 열부터 이전 열의 arr[i][j -1]과 arr[i][j]의 값을 비교햐여, 더 큰 값을 새로운 배열 dp[][]에 누적합하는 방식으로 진행하였습니다.
 
- 참고 -
배열에 자료형을 선언할때, int로 선언하면, 지정되지 않은 부분은 0으로 채워지고, Integer로 선언하면 지정되지 않은 부분은 null값이 채워지게 됩니다.

 

Top-Down VS Bottom-Up

---

탑다운 방식은 메모이제이션을 사용해서 큰 부분부터 작은 부분까지 쪼개어 계산하는 방식이고, 바텀업 방식은 반복문을 사용해서 작은 부분부터 합쳐가며 큰 부분까지 계산하는 방식입니다. 두 개의 방식을 표로 정리해보겠습니다. 분명 메모리나 실행 속도에서 차이가 있을 텐데요, 표로 정리해보았습니다.

Top-Down / Bottom-Up 비교 표

 
Top-Down 코드와 Bottom-Up 코드의 실행 결과도 보여드리겠습니다.

위부터 차례대로 Top-Down, Bottom-Up

실제로 Top-Down방식(재귀 함수 호출)이 2MB정도의 메모리를 더 차지했다는 사실을 알 수 있습니다. 크게 유의미한 차이는 아닌것 같습니다.

 

코드 해석

---

Bottom-up 코드와 Top-Down코드의 입력은 2차원배열을 사용하여 같고, dp 2차원 배열에 값을 담는 방식만 다릅니다.

위의 내용을 토대로 보시면 코드 해석은 어렵지 않을것이라고 생각합니다.