C++ 다이나믹 프로그래밍으로 삼각형 최소 경로 합 구하기

삼각형이 하나 주어졌을 때, 꼭대기에서 바닥까지 내려가는 최소 경로 합(minimum path sum)을 구하는 문제를 살펴보겠습니다. 각 단계마다 아래 행에 있는 인접한 숫자로만 이동할 수 있다는 조건이 있습니다.

예를 들어, 다음과 같은 삼각형이 있다고 가정해 봅시다.

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

이 경우 꼭대기에서 바닥까지의 최소 경로 합은 11입니다. 즉, 2 + 3 + 5 + 1 = 11이 됩니다.

해결 접근 방식

이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 알고리즘의 단계는 다음과 같습니다.

• 동적 계획법에 사용할 DP 테이블(배열)을 하나 생성합니다.
• n := 삼각형의 크기로 설정합니다.
• i := n - 2부터 0까지 역순으로 반복합니다.
  • j := 0부터 i까지 반복합니다.
    • dp[j] := triangle[i][j] + dp[j]와 dp[j+1] 중 작은 값으로 갱신합니다.
• 최종적으로 dp[0]을 반환합니다.

C++ 예제 코드

아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector <int> dp(triangle.back());
        int n = triangle.size();
        for(int i = n - 2; i >= 0; i--){
            for(int j = 0; j <= i; j++){
                dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]);
            }
        }
        return dp[0];
    }
};
main(){
    Solution ob;
    vector<vector<int> > v = {{2},{3,4},{6,5,7},{4,1,8,3}};
    cout << ob.minimumTotal(v);
}

입력

[[2],[3,4],[6,5,7],[4,1,8,3]]

출력

11

코드 설명

이 코드의 핵심은 바닥 행부터 위로 거슬러 올라가며 각 위치에서 도달 가능한 최소 합계를 누적하는 것입니다. dp 배열은 처음에 삼각형의 마지막 행으로 초기화되고, 이후 위쪽 행으로 이동하면서 현재 위치의 값과 아래 두 인접 위치(dp[j], dp[j+1]) 중 작은 값을 더해 갱신됩니다.

모든 반복이 끝나면 dp[0]에는 꼭대기에서 시작하는 최소 경로 합이 저장되어 있으므로, 이를 그대로 반환하면 됩니다. 시간 복잡도는 O(n²), 공간 복잡도는 O(n)으로 매우 효율적인 방식입니다.