C++로 풀어보는 삼각형 최소 합 경로 문제

문제 정의

숫자로 이루어진 삼각형 구조가 주어졌을 때, 꼭대기에서 바닥까지 내려가는 경로 중 합이 가장 작은 경로의 값을 구하는 것이 목표입니다. 이동할 때에는 반드시 아래 행에 있는 인접한 숫자로만 움직일 수 있습니다.

예제

입력이 다음과 같다고 가정해 보겠습니다.

이 경우 최소 합은 13이며, 해당 경로는 다음과 같습니다.

5 + 3 + 1 + 4 = 13

알고리즘 접근 방식

동적 계획법(Dynamic Programming)의 메모이제이션 기법을 활용합니다.
메모이제이션에 사용할 1차원 배열을 하나 생성합니다.
삼각형의 아래쪽 행부터 위쪽으로 거슬러 올라가며 각 행 K에 대해 다음 점화식을 적용합니다.

memorization[i] = min(memorization[i], memorization[i+1]) + A[k][i];

즉, 현재 위치에서 선택할 수 있는 두 개의 인접 값 중 더 작은 값을 골라 자기 자신과 더하는 방식입니다. 마지막 행부터 시작해 위로 올라갈수록 각 위치에서의 최소 경로 합이 누적되며, 최종적으로 배열의 첫 번째 요소에 전체 최소 합이 저장됩니다.

C++ 구현 예제

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

int getMinSum(vector<vector<int>> &arr) {
   int memorization[arr.size()];
   int n = arr.size() - 1;

   // 마지막 행의 값으로 초기화
   for (int i = 0; i < arr[n].size(); ++i) {
      memorization[i] = arr[n][i];
   }

   // 아래에서 위로 올라가며 최소 합 계산
   for (int i = arr.size() - 2; i >= 0; --i) {
      for (int j = 0; j < arr[i + 1].size() - 1; ++j) {
         memorization[j] = arr[i][j] +
         min(memorization[j], memorization[j + 1]);
      }
   }
   return memorization[0];
}

int main() {
   vector<vector<int>> arr = {
   {5},
   {7, 3},
   {8, 1, 2},
   {9, 6, 4, 5}};

   cout << "Minimum sum path = " << getMinSum(arr) << endl;
   return 0;
}

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

실행 결과

Minimum sum path = 13

정리

이 문제는 모든 경로를 탐색하는 완전 탐색 방식으로도 해결할 수 있지만, 경로의 수가 지수적으로 증가하기 때문에 비효율적입니다. 반면 위와 같은 하단부터 상단으로 올라가는 동적 계획법을 사용하면 시간 복잡도 O(n²), 공간 복잡도 O(n)으로 효율적으로 해결할 수 있습니다. 추가 배열 없이 입력 삼각형 자체를 갱신하는 방식으로 공간을 더욱 절약할 수도 있습니다.