[Programmers] #43105 - 정수 삼각형 [Java][C++][Python]

문제 링크

---

1. 아이디어

삼각형의 각 칸까지 도달하는 경로 중 합이 최대인 값을 dp[i][j]에 저장하는 전형적인 DP 문제다. 삼각형 구조상 $(i, j)$ 칸에는 바로 위 행의 $(i-1, j-1)$ 또는 $(i-1, j)$ 칸에서만 내려올 수 있으므로, 두 후보 중 더 큰 값에 현재 칸의 값을 더한 dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i-1][j-1]로 점화식을 세울 수 있다. 삼각형의 양 끝(각 행의 첫 칸과 마지막 칸)은 두 후보 중 하나가 삼각형 범위를 벗어나는데, dp 배열이 기본값 0으로 초기화돼 있어 존재하지 않는 칸을 0으로 취급하는 효과를 내므로 별도 예외 처리 없이 같은 점화식을 그대로 적용해도 된다. 이렇게 삼각형의 가장 아래 행까지 dp를 채우면 각 dp[n][j]는 꼭대기에서 그 칸까지 내려오는 경로의 최대 합을 뜻하므로, 마지막 행에서 가장 큰 값이 곧 꼭대기부터 바닥까지의 최대 경로 합이 된다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N^2)$	$O(N^2)$

($N$ = 삼각형의 높이)

---

3. 코드

풀이 [Java][C++][Python]

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

        for (int i = 1; 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 - 1][j - 1];
            }
        }

        int max = 0;
        for (int x : dp[n]) {
            max = Math.max(max, x);
        }

        return max;
    }
}

#include <bits/stdc++.h>
using namespace std;

int solution(vector<vector<int>> triangle) {
    int n = triangle.size();
    vector<vector<int>> dp(1 + n, vector<int>(1 + n));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i - 1][j - 1];
        }
    }

    return *max_element(dp[n].begin(), dp[n].end());
}

def solution(triangle):
    n = len(triangle)
    dp = [[0] * (1 + n) for _ in range(1 + n)]

    for i in range(1, 1 + n):
        for j in range(1, 1 + i):
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i - 1][j - 1]

    return max(dp[n])

---