[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 이상이기에 존재하지 않는 칸을 0으로 취급하는 효과를 내므로 별도 예외 처리 없이 같은 점화식을 그대로 적용해도 된다. 이렇게 삼각형의 가장 아래 행까지 dp를 채우면 각 dp[n][j]는 꼭대기에서 그 칸까지 내려오는 경로의 최대 합을 뜻하므로, 마지막 행에서 가장 큰 값이 곧 꼭대기부터 바닥까지의 최대 경로 합이 된다.

---

2. 복잡도

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

($N$ = triangle의 행 수)

---

3. 코드

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

import java.util.*;

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];
            }
        }

        return Arrays.stream(dp[n]).max().getAsInt();
    }
}

#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, n + 1):
        for j in range(1, i + 1):
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i - 1][j - 1]

    return max(dp[n])

---