[백준] 1932번 - 정수 삼각형

 

1932번: 정수 삼각형

 

 

정수 삼각형의 맨 위층에 놓인 수부터 출발하여 맨 아래층으로 내려올 때, 지나온 경로에 놓인 수를 모두 더한 합이 최대가 되는 경로를 구하는 문제이다. 

 

완전 탐색으로도 풀 수 있지만 문제 특성상 메모제이션을 사용하는 다이나믹프로그래밍을 사용할 수도 있다. 맨 위에서 출발 하여 아래로 내려올 때 현재 위치에서 아래층으로 이동할 수 있는 경로는 두 가지 뿐이다. 현재 위치의 대각선 왼쪽 또는 대각선 오른쪽. 이때 층을 내려가는게 아닌 층을 올라온다고 생각하면 

i) 현재 위치의 대각선 왼쪽 경로로 올라왔을 때 합의 최대

ii) 현재 위치의 대각선 오른쪽 경로로 올라왔을 때 합의 최대

위 두 경우 중 더 큰 값에 현재 위치한 곳의 정수를 더한 합을 dp[][]에 저장하고, 해당 경로에 대한 최대값이 또 필요하다면 경로의 합을 다시 계산할 필요 없이 저장한 값을 바로 사용할 수 있다.

 

 

 

 

전체 코드

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

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));
        StringTokenizer st = null;
        
        int n = Integer.parseInt(br.readLine());
        
        arr = new int[n][n];
        dp = new Integer[n][n];
        
        
        for (int i=0; i<n; i++) {
            
            st = new StringTokenizer(br.readLine(), " ");
            
            for (int j=0; j<i+1; j++) arr[i][j] = Integer.parseInt(st.nextToken());
        }
        
        // 가장 아래층에 해당하는 값들은 dp에 미리 넣어주어서 recur함수가 재귀에서 빠져나오도록한다.
        for (int i=0; i<n; i++) dp[n-1][i] = arr[n-1][i];
        
        
        
        System.out.println(recur(0, 0));
        
        br.close();
    }
    
    static int recur(int step, int N) {
        
        if (dp[step][N] == null) {
        // 현재 위치에서 대각선 왼쪽 아래까지의 합의 최대와 대각선 오른쪽 아래까지의 합의 최대 중 더 큰 값을 택한다.
            dp[step][N] = arr[step][N] + Math.max(recur(step+1 ,N), recur(step+1, N+1));
        }
        
        return dp[step][N];
    }
}

 

 

 

추가로 이 문제의 최초 풀이를 확인해보니 왜인지 모르겠으나 이중 배열이 아닌 1차원 배열로 풀었던 것을 확인했다. 여러 문제를 오랜시간 풀다보면 집중력이 떨어져서 쉬운 길을 두고 멀리 돌아가서 해결하는 경우도 종종 있는데 적당한 휴식의 중요성을 다시한번 느낀다.

 

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

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));
        StringTokenizer st = null;
        
        int n = Integer.parseInt(br.readLine());
        
        int size = 0;
        
        for (int i=1; i<=n; i++) {
        	size += i;
        }
        
        arr = new int[size];
        dp = new Integer[size];
        
        int idx = 0;
        
        for (int i=0; i<n; i++) {
            
            st = new StringTokenizer(br.readLine(), " ");
            
            while(st.hasMoreTokens()) {
                arr[idx] = Integer.parseInt(st.nextToken());
                if (i == n-1) {
                    dp[idx] = arr[idx];
                }
                idx++;
            }
        }
        
        recur(1, 0);
        
        System.out.println(dp[0]);
        
        br.close();
    }
    
    static int recur(int step, int N) {
        
        if (dp[N] == null) {
            dp[N] = arr[N] + Math.max(recur(step+1 ,N+step), recur(step+1, N+step+1));
        }
        
        return dp[N];
    }
}