[백준/DP] 1932번 정수 삼각형 (JAVA)

문제

풀이

1. 2번째 줄부터 n번째 줄까지 차례로 탐색해가며 각 dp[i][j]를 최댓값으로 만든다.
   • 왼쪽과 오른쪽 대각선 위에 있는 값들 중 더 큰 dp 값을 현재 triangle 값과 합하면 최댓값이다.
2. dp[n] 배열의 값들 중 최댓값이 정답이다.

코드

import java.io.*;

public class Main {

    private static final int MAXIMUM = 500;

    private static int n;
    private static int[][] triangle = new int[MAXIMUM + 1][MAXIMUM + 1];
    private static int[][] dp = new int[MAXIMUM + 1][MAXIMUM + 1];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        for (int i = 1; i <= n; i++) {
            String[] line = br.readLine().split(" ");
            for (int j = 1; j <= i; j++) {
                triangle[i][j] = Integer.parseInt(line[j - 1]);
            }
        }

        dp();
        bw.append(String.valueOf(getMax()));

        br.close();
        bw.close();
    }

    private static void dp() {
        dp[1][0] = 0;
        dp[1][1] = triangle[1][1];
        for (int i = 2; i <= n; i++)
            for (int j = 1; j <= i; j++)
                dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
    }

    private static int getMax() {
        int max = 0;
        for (int val : dp[n])
            max = Math.max(max, val);
        return max;
    }
}