C++로 삼각형 최소 경로 합 구하기 – 동적 계획법(DP) 완벽 가이드

삼각형 형태의 숫자 배열이 주어졌을 때, 꼭대기에서 바닥까지 이동하는 최소 경로 합을 구하는 문제를 살펴보겠습니다. 이동 규칙은 간단합니다. 각 단계에서 바로 아래 행에 있는 인접한 숫자로만 이동할 수 있습니다.

문제 예시

다음과 같은 삼각형이 있다고 가정해 보겠습니다.

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

이 경우 꼭대기에서 바닥까지의 최소 경로 합은 11입니다. 실제 경로는 2 → 3 → 5 → 1이며, 이들의 합이 정확히 11이 됩니다.

해결 접근 방식: 동적 계획법

이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 아래에서 위로 거슬러 올라가면서 각 위치에서 도달 가능한 최소 합을 누적하는 것입니다.

알고리즘 단계

• 삼각형의 마지막 행을 복사하여 DP 테이블(dp)을 생성합니다.
• n := 삼각형의 행 개수
• i를 n - 2부터 0까지 감소시키며 반복합니다.
  • j를 0부터 i까지 반복하며 다음을 수행합니다.
    • dp[j] := triangle[i][j] + min(dp[j], dp[j + 1])
• 최종적으로 dp[0]을 반환합니다. 이것이 곧 최소 경로 합입니다.

마지막 행부터 시작해 위로 올라갈 때마다, 현재 위치의 값과 그 아래 두 인접 값 중 작은 쪽을 더해 나가는 방식입니다. 이렇게 하면 별도의 2차원 배열 없이 1차원 배열만으로 공간 복잡도 O(n)에 문제를 해결할 수 있습니다.

C++ 구현 예제

class Solution {
    public:
    void printVector(vector <int>& v){
        for(int i = 0; i < v.size(); i++) cout << v[i] << " ";
        cout << endl;
    }
    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]);
            }
            // printVector(dp);
        }
        return dp[0];
    }
};

입력

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

출력

11

복잡도 분석

• 시간 복잡도: O(n²) — 삼각형의 모든 원소를 한 번씩 방문합니다.
• 공간 복잡도: O(n) — 마지막 행 크기의 1차원 배열만 추가로 사용합니다.

이처럼 동적 계획법을 활용하면 모든 경로를 탐색하는 비효율적인 완전 탐색(지수 시간) 대신, 선형 공간 안에서 빠르게 최적해를 구할 수 있습니다.