C++에서 행렬의 각 행에서 선택한 요소의 최대 합 구하기

이 문제에서는 2차원 행렬 mat[][]가 주어집니다. 우리의 과제는 C++로 행렬의 각 행에서 요소를 하나씩 선택하여 만들 수 있는 최대 합을 구하는 프로그램을 작성하는 것입니다.

문제 설명

행렬의 각 행에서 하나의 요소를 선택할 때, 현재 행에서 선택한 요소는 바로 아래 행에서 선택한 요소보다 커야 한다는 조건이 있습니다. 이 조건을 만족하면서 얻을 수 있는 최대 합을 구하고, 조건을 만족하는 선택이 불가능한 경우에는 -1을 출력합니다.

예제를 통해 문제를 자세히 이해해 보겠습니다.

입력

mat[][] = {{4, 6, 1},
{2, 5, 7},
{9, 1, 2}}

출력

22

설명

1번째 행 = 6
2번째 행 = 7
3번째 행 = 9
합계 = 6 + 7 + 9 = 22

풀이 접근 방법

가장 간단한 해결 방법은 행렬의 마지막 행부터 시작하는 것입니다. 먼저 마지막 행에서 가장 큰 수를 찾아 MaxSum에 더한 뒤, 한 행 위로 이동하여 바로 아래 행에서 선택한 최댓값보다 작은 수 중에서 가장 큰 값을 찾습니다. 이 과정을 맨 윗행에 도달할 때까지 반복합니다. 만약 어떤 행에서도 아래 행의 최댓값보다 작은 수를 찾지 못한다면, 조건을 만족하는 합을 만들 수 없으므로 -1을 반환합니다.

이 알고리즘의 시간 복잡도는 O(row × col)이며, 추가적인 저장 공간이 필요하지 않아 공간 복잡도는 O(1)입니다.

예제 코드

아래 프로그램은 위 풀이의 동작 과정을 보여줍니다.

#include <iostream>
using namespace std;
#define row 3
#define col 3

int RowMaxSum(int a[row][col]){
    int maxValLastRow = 10000;
    int maxSum = 0;
    for (int i = row - 1; i >= 0; i--){
        int maxNo = -1;
        for (int j = 0; j < col; j++)
            if (maxValLastRow > a[i][j] && a[i][j] > maxNo)
                maxNo = a[i][j];
        if (maxNo == -1)
            return -1;
        maxValLastRow = maxNo;
        maxSum += maxValLastRow;
    }
    return maxSum;
}
int main(){
    int a[3][3] = {{4, 6, 1},
                   {2, 5, 7},
                   {9, 1, 2}};
    cout<<"행렬의 각 행에서 선택한 요소의 최대 합은 "<<RowMaxSum(a);
    return 0;
}

출력 결과

행렬의 각 행에서 선택한 요소의 최대 합은 22