[프로그래머스] 정수 삼각형 - Java

• 프로그래머스 문제 URL

---

문제 요약

삼각형 모양의 triangle 배열이 주어질 때, 맨 꼭대기에서 맨 아래까지 내려가며 얻을 수 있는 최대 합을 구하는 문제다.
각 칸은 아래의 왼쪽 아래 / 오른쪽 아래 중 한 칸으로만 내려갈 수 있다.

---

핵심 아이디어

각 칸의 최대합은 “그 칸에서 내려갈 수 있는 두 칸 중 더 큰 값”에 현재 칸 값을 더한 것뿐이다.
즉, 아래층의 최적해를 위로 전파하는 방식으로 아래에서 위로(bottom-up) 채우면 된다.

이 문제의 장점은 입력이 이미 “삼각형 테이블” 형태로 딱 주어져 있어서, 별도 그래프 변환 없이 바로 DP 테이블로 활용할 수 있다.

---

DP 정의 & 점화식

dp 정의(뒤집기 방식)

• dp[i][j] = i행 j열에서 **아래로 내려가며** 얻을 수 있는 최대 합
• 최종 답은 dp[0][0] (꼭대기에서 최대합)

초기값(맨 아래 줄)

맨 마지막 행은 더 내려갈 곳이 없으므로:

for (int j = 0; j < triangle[n-1].length; j++) {
    dp[n-1][j] = triangle[n-1][j];
}

점화식(아래→위 전파)

각 칸은 아래의 두 칸 중 더 큰 쪽으로 내려간다.

dp[i][j] = triangle[i][j] + max(dp[i+1][j], dp[i+1][j+1])

반복 범위는 i = n-2부터 i = 0까지(맨 마지막 줄은 이미 처리했으므로).

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

---

왜 i = n-2부터 시작하나?

• i = n-1(마지막 행)은 이미 dp[n-1][j] = triangle[n-1][j]로 채워놨음.
• i = n-2부터 시작해서 dp[n-2][j]를 계산할 때, dp[n-1]의 값을 참조한다.
• 점화식에서 dp[i+1]을 참조하므로, 이미 계산된 아래층이 있어야 함.

---

전체 코드(제출용)

class Solution {
    public int solution(int[][] triangle) {
        int n = triangle.length;
        int[][] dp = new int[n][n];

        // 맨 마지막 줄은 그대로 복사
        for (int j = 0; j < n; j++) {
            dp[n - 1][j] = triangle[n - 1][j];
        }

        // 아래에서 위로 올라가며 채우기
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = triangle[i][j] + Math.max(dp[i + 1][j], dp[i + 1][j + 1]);
            }
        }

        return dp[0][0]; // 꼭대기에서 최대합
    }
}

원하면 이걸 더 줄여서 triangle 배열 자체를 덮어쓰는 버전(추가 dp 배열 없이)도 블로그에 같이 붙여줄게.