이 문제에서는 역삼각형 형태로 배치된 숫자들이 주어지며, 이 삼각형 안에서 만들 수 있는 최대 경로 합을 찾는 프로그램을 작성해야 합니다.
문제 개요
역삼각형 형태의 숫자 배열은 첫 번째 행에 n개의 요소가 있고, 두 번째 행에는 n-1개, 세 번째 행에는 n-2개가 있는 식으로 한 줄씩 줄어드는 구조입니다.
우리의 목표는 각 행에서 하나의 요소씩 선택해 더할 때 얻을 수 있는 최대 합을 구하는 것입니다.
입력 예시
5 1 9 3 6 2
출력 예시
17
설명
마지막 행에서 맨 위 행까지 경로를 따라 올라가면서, 경로에 포함되는 요소들의 합이 최대가 되도록 선택합니다. 위 예시에서는 9 → 6 → 2 경로를 따라 9 + 6 + 2 = 17이 최대 합이 됩니다.
접근 방법: 동적 프로그래밍(DP)
이 문제는 최소 비용 경로 문제에서 활용되는 방식과 유사한 동적 프로그래밍(Dynamic Programming) 기법으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 먼저 역삼각형의 모든 숫자를 왼쪽으로 밀어 붙여 일반적인 정사각 행렬 형태로 변환하고, 빈자리는 0으로 채웁니다.
- 맨 아래 행에서부터 위로 올라가며, 각 요소에 바로 아래 행에 위치한 인접한 두 요소 중 더 큰 값을 더합니다.
- 첫 번째 열의 경우에는 인접한 왼쪽 요소가 없으므로 바로 아래 요소만 더합니다.
- 이렇게 누적된 값들 중 최댓값이 곧 최대 경로 합이 됩니다.
C++ 구현 코드
다음은 역삼각형에서 최대 경로 합을 찾는 C++ 프로그램입니다.
#include <iostream>
using namespace std;
#define N 3
int findMaxPathSumInvertedTriangle(int matrix[][N]){
int maxSum = 0;
for (int i = N - 2; i >= 0; i--) {
for (int j = 0; j < N - i; j++) {
if (j - 1 >= 0)
matrix[i][j] += max(matrix[i + 1][j], matrix[i + 1][j - 1]);
else
matrix[i][j] += matrix[i + 1][j];
maxSum = max(maxSum, matrix[i][j]);
}
}
return maxSum;
}
int main(){
int invertedTriangle[N][N] = {
{5, 1, 9},
{3, 6, 0},
{2, 0, 0}};
cout<<"The maximum path sum is "<<findMaxPathSumInvertedTriangle(invertedTriangle);
return 0;
}실행 결과
The maximum path sum is 17
프로그램을 실행하면 역삼각형에서 구할 수 있는 최대 경로 합인 17이 출력됩니다. 이 접근 방식은 삼각형의 크기가 커져도 각 요소를 한 번씩만 처리하므로 O(N²)의 시간 복잡도로 효율적으로 동작합니다.