C++로 해결하는 직각 삼각형 최대 경로 합 문제

문제 설명

숫자로 이루어진 직각 삼각형이 주어졌을 때, 꼭대기에서 밑변까지 내려가는 여러 경로 중에서 지나가는 숫자들의 합이 가장 커지는 경로를 찾아 그 최대 합을 구하는 문제입니다.

단, 각 경로에서 다음 숫자는 반드시 바로 아래에 있거나, 아래이면서 한 칸 오른쪽에 위치한 숫자여야 합니다.

예시

입력:
3
4 5
1 10 7

최대 합은 18 (3 + 5 + 10)

알고리즘 접근 방식

핵심 아이디어는 마지막 행(밑변)의 모든 셀에 대해 "그 셀에서 끝나는 경로의 최대 합"을 각각 구한 뒤, 그중 가장 큰 값을 반환하는 것입니다.

각 셀의 최대 합은 바로 위에 있는 두 개의 셀(왼쪽 위, 바로 위)을 재귀적으로 고려하여 계산할 수 있습니다.

그런데 이 과정에서는 동일한 부분 문제가 여러 번 반복해서 계산되는 중복 부분 문제(Overlapping Sub-problems)가 발생합니다. 따라서 동적 계획법(Dynamic Programming)을 활용하면 불필요한 중복 계산 없이 마지막 행의 특정 셀에서 끝나는 최대 합을 효율적으로 구할 수 있습니다.

C++ 구현 예제

#include<bits/stdc++.h>
using namespace std;
int maxSum(int triangle[][3], int n){
    if (n > 1) {
        triangle[1][1] = triangle[1][1] + triangle[0][0];
        triangle[1][0] = triangle[1][0] + triangle[0][0];
    }
    for(int i = 2; i < n; i++) {
        triangle[i][0] = triangle[i][0] + triangle[i-1][0];
        triangle[i][i] = triangle[i][i] + triangle[i-1][i-1];
        for (int j = 1; j < i; j++){
            if (triangle[i][j] + triangle[i-1][j-1] >= triangle[i][j] + triangle[i-1][j]) {
                triangle[i][j] = triangle[i][j] + triangle[i-1][j-1];
            } else {
                triangle[i][j] = triangle[i][j] + triangle[i-1][j];
            }
        }
    }
    int max = triangle[n - 1][0];
    for(int i = 1; i < n; i++) {
        if(max < triangle[n-1][i]) {
            max = triangle[n-1][i];
        }
    }
    return max;
}
int main(){
    int triangle[3][3] = {
        {3},
        {4,5},
        {1,10,7}
    };
    cout << "Maximum sum = " << maxSum(triangle, 3) << endl;
    return 0;
}

동작 원리

위 코드는 입력된 삼각형 배열 자체를 수정하며(bottom-up 방식) 각 셀에 "꼭대기부터 해당 셀까지 도달할 수 있는 최대 누적 합"을 저장합니다. 첫 번째 행과 두 번째 행을 먼저 처리한 뒤, 세 번째 행부터는 왼쪽 끝과 오른쪽 끝 요소를 각각 처리하고, 나머지 중간 요소들은 왼쪽 위 값과 바로 위 값 중 더 큰 것을 선택해 더합니다. 마지막으로 밑변의 모든 값 중 최댓값을 반환합니다.

이 알고리즘의 시간 복잡도는 삼각형의 모든 셀을 한 번씩만 방문하므로 O(n²)이며, 별도의 추가 배열 없이 기존 배열을 그대로 활용하므로 추가 공간 복잡도는 O(1)입니다.

실행 결과

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

Maximum sum = 18