1932 JAVA 정수 삼각형

 

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

코드 과정

접근 방법

1. 삼각형의 아래 대각선으로 더해 최종 가장 큰 값을 결정한다.
2. 입력 값에서 col(x)은 1이 추가가 되고, row(y)는 왼쪽 대각선과 오른쪽 대각선이 각각 (y)와 (y+1) 이 된다. 즉, 저장되어 있는 값이 자기 자신의 위치에서 바로 아래에 위치하거나 그 아래에서 옆으로 1을 이동한 것과 같은 것이다.
3. top-down 방식을 이용하여 최종 맨 아래 행에 합을 저장하여 가장 큰 값을 답으로 선정한다.

틀린 코드

for 문을 사용하지 않고, recursion을 사용했다. for 문을 사용했다면 최대 시간복잡도가 O(n^2) 이기 때문에 시간 초과가 발생하지 않는다. 하지만, recursion의 top-down 방식으로 진행하게 된다면 최대 시간 복잡도는 O(n!)로 큰 값이 도출된다. n의 최대 값은 500이기 때문에 최대 시간 복잡도는 500!가 되는 것이다. 따라서 아래 코드로 문제 접근은 시간초과라는 결과를 초래했다.

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

public class Main{
    public static int[][] arr;
    public static int n;
    public static int max = 0;
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n][n];

        for(int i = 0; i < n ; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int index = 0;
            while(st.hasMoreTokens()){
                arr[i][index++] = Integer.parseInt(st.nextToken());
            }
        }

        // 덧셈 후
        recurPlus(0, 0, 0);

        System.out.println(max);
    }

    public static void recurPlus(int col, int row, int num){
    	
        // 맨 아래에 위치한 경우
        if(col == n){
            max = Math.max(max, num);
            return;
        }

        recurPlus(col + 1, row, arr[col][row] + num); // left
        recurPlus(col + 1, row + 1, arr[col][row] + num); // right
    }
}

맞은 코드

따라서, 이미 저장되어 있는 경우에는 따로 계산을 하지 않는 DP(Dynamic Programming)을 이용했다. 방법은 top-down 에서 bottom-up 방식으로 변경했으며, 현재 위치에서 계산이 안되어 있다면 아래 두 대각선의 결과 값에서 현재 자신의 값을 더한 것이 더 큰 것을 저장한다.

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

public class Main{
    public static int[][] arr;
    public static int[][] dp;
    public static int n;
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n][n];
        dp = new int[n][n];

        for(int i = 0; i < n ; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int index = 0;
            while(st.hasMoreTokens()){
                arr[i][index++] = Integer.parseInt(st.nextToken());
            }
        }
        // bottom up 방식을 사용하기 때문에 마지막 줄에 있는 수를 복사
        for (int i = 0; i < n ; i++){
            dp[n-1][i] = arr[n-1][i];
        }

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


    public static int recurPlus(int col, int row){
    	// 맨 아래에 위치한 경우 자신의 값만을 return
        if(col == n - 1){
            return dp[col][row];
        }

        if(dp[col][row] == 0){
            dp[col][row] = Math.max(recurPlus(col + 1, row), recurPlus(col+1, row+1)) + arr[col][row];
        }

        return dp[col][row];
    }
}