C++의 NxN 그리드에서 최소 합 하강 경로

문제 설명

• NxN 크기의 정수로 구성된 행렬 A가 주어집니다. 작업은 A를 통과하는 낙하 경로의 최소 합을 찾는 것입니다.
• 하강 경로는 첫 번째 행의 모든 ​​요소에서 시작하여 마지막 행에서 끝납니다.
• 각 다음 행에서 하나의 요소를 선택합니다. 다음 행의 선택은 이전 행의 열과 최대 1만큼 다른 열에 있어야 합니다.

예시

If N = 2 and matrix is:
{
   {5, 10},
   {25, 15}
} then output will be 20 as element 5 and 15 are selected

예시

#include <bits/stdc++.h>
#define MAX 2
using namespace std;
int getMinSumPath(int matrix[MAX][MAX]) {
   for (int row = MAX - 2; row >= 0; --row) {
      for (int col = 0; col < MAX; ++col) {
         int val = matrix[row + 1][col];
         if (col > 0) {
            val = min(val, matrix[row +1][col - 1]);
         }
         if (col + 1 < MAX) {
            val = min(val, matrix[row +1][col + 1]);
         }
         matrix[row][col] = matrix[row][col] +val;
      }
   }
   int result = INT_MAX;
   for (int i = 0; i < MAX; ++i)
   result = min(result, matrix[0][i]);
   return result;
}
int main() {
   int matrix[MAX][MAX] = {
      {5, 10},
      {25, 15},
   };
   cout << "Minimum sum path = " << getMinSumPath(matrix)
   << endl;
   return 0;
}

위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다.

출력

Minimum sum path = 20