C++ 동적 계획법으로 풀어보는 행렬 최대 합 경로 문제

문제 정의

n×n 크기의 행렬이 있고, 각 칸에는 특정 값이 할당되어 있다고 가정합니다. 우리는 i번째 행의 어떤 칸에서든 (i+1)번째 행의 대각선 방향 칸으로만 이동할 수 있습니다. 즉, cell(i, j)에서는 cell(i+1, j-1) 또는 cell(i+1, j+1) 두 곳으로만 이동이 가능합니다. 이 규칙을 지키면서 첫 번째 행에서 마지막 행까지 내려가는 경로 중, 지나가는 칸 값들의 합이 최대가 되는 경로를 찾는 것이 이 문제의 목표입니다.

예시

입력이 다음과 같다고 가정해 봅시다:
{
   {5, 6, 1, 17},
   {-2, 10, 8, -1},
   { 3, -7, -9, 4},
   {12, -4, 2, 2}
}

이 경우 최대 합은 (17 + 8 + 4 + 2) = 31입니다.

알고리즘

• 첫 번째 행의 각 칸에서 출발하는 모든 경로에 대해 최대 합을 계산한 뒤, 그중 가장 큰 값을 반환하는 것이 기본 아이디어입니다.

• 동일한 하위 문제의 결과를 여러 번 재사용해야 하므로 동적 계획법(Dynamic Programming)을 활용합니다.

접근 방식 상세

가장 아래쪽 행부터 거꾸로 위로 올라가며 DP 테이블을 채워 나갑니다. 여기서 dp[i][j]는 (i, j) 칸에서 시작하여 마지막 행까지 도달했을 때 얻을 수 있는 최대 합을 의미하며, 점화식은 다음과 같습니다.

dp[i][j] = mat[i][j] + max(dp[i+1][j-1], dp[i+1][j+1])

단, 행렬의 범위를 벗어나는 열 인덱스는 계산에서 제외해야 합니다. 모든 테이블을 채운 후 dp[0][j] 값들 중 최댓값이 곧 전체 경로의 최대 합이 됩니다. 시간 복잡도와 공간 복잡도는 각각 O(n²)입니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
#define SIZE 10
int getMaxMatrixSum(int mat[SIZE][SIZE], int n){
   if (n == 1) {
      return mat[0][0];
   }
   int dp[n][n];
   int maxSum = INT_MIN, max;
   for (int j = 0; j < n; j++) {
      dp[n - 1][j] = mat[n - 1][j];
   }
   for (int i = n - 2; i >= 0; i--) {
      for (int j = 0; j < n; j++) {
         max = INT_MIN;
         if (((j - 1) >= 0) && (max < dp[i + 1][j - 1])) {
            max = dp[i + 1][j - 1];
         }
         if (((j + 1) < n) && (max < dp[i + 1][j + 1])) {
            max = dp[i + 1][j + 1];
         }
         dp[i][j] = mat[i][j] + max;
      }
   }
   for (int j = 0; j < n; j++) {
      if (maxSum < dp[0][j]) {
         maxSum = dp[0][j];
      }
   }
   return maxSum;
}
int main(){
   int mat[SIZE][SIZE] = {
      {5, 6, 1, 17},
      {-2, 10, 8, -1},
      {3, -7, -9, 4},
      {12, -4, 2, 2}
   };
   int n = 4;
   cout << "Maximum Sum = " << getMaxMatrixSum(mat, n) << endl;
   return 0;
}

실행 결과

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

Maximum Sum = 31