C++로 구현하는 삼각형 최대 경로 합 찾기

이 문제에서는 삼각형 형태로 배치된 숫자들이 주어지며, 이 삼각형 안에서 최대 경로 합(maximum path sum)을 찾는 프로그램을 작성하는 것이 목표입니다.

삼각형의 요소들은 첫 번째 행에 1개의 요소가 배치되고, 그다음 행부터는 요소의 개수가 하나씩 증가하며 n번째 행까지 채워지는 구조입니다.

프로그램은 삼각형 내에서 요소들의 합이 가장 커지는 경로를 찾아야 합니다. 즉, 꼭짓점에서 시작해 아래 행으로 이동하면서 만들 수 있는 경로 중 합이 최대가 되는 경로를 구하는 것입니다.

문제 예시

예제를 통해 문제를 살펴보겠습니다.

입력 −

  1
 5 6
8 2 9

출력 − 16

설명 −

꼭짓점에서 시작하는 경로 중 최대 합을 반환하는 경로는 다음과 같습니다.

9 + 6 + 1 = 16

풀이 접근 방식

이 문제는 동적 계획법(Dynamic Programming)을 활용한 상향식(bottom-up) 접근으로 해결할 수 있습니다.

먼저 삼각형의 모든 숫자를 왼쪽 정렬하고, 각 행의 끝에 0을 채워 넣습니다. 그러면 삼각형이 '최소 비용 경로' 문제에서 볼 수 있는 것과 유사한 행렬 형태로 변환됩니다.

이후 가장 아래 행부터 시작하여, 각 요소마다 가능한 모든 경로를 확인하고 해당 요소까지 도달할 수 있는 최대 합을 선택합니다. 이 과정을 위쪽 행으로 거슬러 올라가며 반복하면, 마침내 삼각형 꼭짓점에 저장된 값이 곧 경로의 최대 합이 됩니다.

구현 예제

삼각형의 최대 경로 합을 찾는 프로그램 −

#include<iostream>
using namespace std;
#define N 3
int findMaxPathSumTriangle(int mat[][N], int m, int n){
   for (int i=m-1; i>=0; i--){
      for (int j=0; j<=i; j++){
         if (mat[i+1][j] > mat[i+1][j+1])
            mat[i][j] += mat[i+1][j];
         else
            mat[i][j] += mat[i+1][j+1];
      }
   }
   return mat[0][0];
}
int main() {
   int triangle[N][N] = {
      {1, 0, 0},
      {5, 6, 0},
      {8, 2, 9} };
   cout<<"The maximum path sum in triangle is "<<findMaxPathSumTriangle(triangle, 2, 2);
   return 0;
}

실행 결과

The maximum path sum in triangle is 16