백준 1932. 정수 삼각형 :: 돼지개발자

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

"DP, bottom-up / DP라고 무조건 재귀 생각하지말자."

알고리즘은 삼각형의 맨 밑부분부터 시작해서 dp 갱신을 시작한다. 처음에 재귀로 구현했는데 시간초과가 났다. dp 값을 비교해서 기존 dp 값보다 작으면 탐색하지 못하게 하였는데??? 라고 생각했다. dp 값이 나중에 큰 값으로 갱신된다면, 이전 까지 탐색 경로들은 그냥 지나칠 거임..

따라서 해당 지점에 가능한 가장 큰 값이 맨 나중에 갱신되는 데이터가 주어졌다면 아마 dp 값 비교를 통한 가지치기는 적용 안될듯.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
class Main {
 
    static int n;
    static int[][] map;
    static int[][] dp;
    
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        
        dp = new int[n][n];
        
        map = new int[n][n];
        
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            for (int j = 0; j < i+1; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        // 사각형의 맨 아래 부분에 dp 값을 갱신한다.
        for (int i = 0; i < n; i++) {
            dp[n-1][i] = map[n-1][i];
        }
        
        // 삼각형 밑바닥 부터 dp값을 갱신하며 올라간다.
        for (int i = n-2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                // 하위 노드 두개에 대해 큰값을 선택한다.
                dp[i][j] = map[i][j] + Math.max(dp[i+1][j],dp[i+1][j+1]);
            }
        }
        System.out.println(dp[0][0]);
    }
    
}