[BJ] 1932. 정수 삼각형

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

1932번: 정수 삼각형

 

그동안 제일 취약했던 DP문제들을 풀어볼 생각이다..

 

이 문제에서는

맨 위층부터 시작해서 아래에 있는 수 중 하나를 택하며 아래층으로 내려올 때

1) 현재 수의 바로 밑에 있는 수 2) 대각선 오른쪽 아래에 있는 수 들 중에서만 택할 수 있다.

 

즉, arr[i][j]를 택할 수 있는 위치는

1) 바로 위의 수 2) 대각선 왼쪽 위에 있는 수들이다.
1), 2) 의 위치에서 더 큰 합을 가지는 경우를 택하여 arr[i][j]의 수를 더해주면 (i, j)번째의 최적의 합이 된다.

다만

1. j=0인 경우 대각선 왼쪽 위에 수가 없으므로 0으로 계산한다.
2. i=j인 경우 바로 위에 숫자가 없으므로 0으로 계산한다.

 

import java.io.*;
import java.util.*;
// 210606

public class Main_BJ_1932_정수삼각형 {
    static int N;
    static int[][] dp;
    public static void main(String[] args) throws Exception {
        //System.setIn(new FileInputStream("src/res/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = stoi(br.readLine());

        dp = new int[N][N];
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=0; j<i+1; j++) {
                dp[i][j] = stoi(st.nextToken());
            }
        }
        
        // 다이나믹 프로그래밍으로 2번째 줄 부터 내려가면서 확인
        for(int i=1; i<N; i++) {
            for(int j=0; j<i+1; j++) {
                int upLeft, up;
                // 왼쪽 위에서 내려오는 경우
                if(j==0) upLeft = 0;
                else upLeft = dp[i-1][j-1];
                // 바로 위에서 내려오는 경우
                if(j==i) up = 0; // 위에가 없음
                else up = dp[i-1][j];
                // 최대 합 저장
                dp[i][j] = dp[i][j] + Math.max(upLeft, up);
            }
        }

        int ans = 0;
        // 맨 마지막 줄의 값 중 최대값이 답
        for(int j=0; j<N; j++) {
            ans = Math.max(ans, dp[N-1][j]);
        }
        System.out.println(ans);
    }

    static int stoi(String str) {
        return Integer.parseInt(str);
    }
}