[백준] 1932 - 정수 삼각형 | Java

짱챌·2025년 4월 17일

DP 백준

Algorithm

목록 보기

8/19

📌 문제 정보

[1932번: 정수 삼각형]

💡 접근 방식

dp 배열을 만들어, Bottom-Up 방식으로 풀어나가면 된다.
i층 j번 숫자는

i+1층 j번(left)으로 내려가거나
i+1층 j+1번(right)으로 내려갈 수 있다.

따라서, i층 j번까지의 누적합을 기준으로 다음 층의 left와 right에서의 최대값을 갱신해나가면 된다.

✅ 코드

import java.util.*;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

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

        int[][] tri = new int[n][n];
        int[][] dp = new int[n][n];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j<=i; j++) {
                tri[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = tri[i][j];
            }
        }
        if (n == 1) {
            System.out.println(tri[0][0]);
            return;
        }


        dp[0][0] = tri[0][0];
        dp[1][0] = tri[0][0] + tri[1][0];
        dp[1][1] = tri[0][0] + tri[1][1];

        for (int i = 1; i < n-1; i++) {
            for (int j = 0; j <= i; j++) {

                int left = dp[i][j] + tri[i + 1][j];
                int right = dp[i][j] + tri[i + 1][j+1];

                dp[i + 1][j] = Math.max(dp[i + 1][j], left);
                dp[i + 1][j+1] = Math.max(dp[i + 1][j+1], right);

            }
        }

        int result = 0;
        for (Integer i : dp[n - 1]) {
            result = Math.max(result, i);
        }


        System.out.println(result);
    }
}