문제 개요
이 문제에서는 크기가 n×m인 2차원 행렬이 주어집니다. 우리가 해야 할 일은 n개의 배열(행)에서 증가하는 순서를 이루는 요소들을 선택했을 때 얻을 수 있는 최대 합을 구하는 프로그램을 작성하는 것입니다.
문제 설명
각 행에서 요소를 하나씩 선택하여 합을 만들되, i번째 행에서 선택한 요소는 반드시 (i+1)번째 행에서 선택한 요소보다 작아야 합니다. 이러한 조건을 만족하는 조합이 존재하지 않는다면, 가능한 결과가 없다는 의미로 -1을 반환해야 합니다.
예시로 이해하기
입력:
mat[][] = {
{4, 5, 1, 3, 6},
{5, 9, 2, 7, 12},
{13, 1, 3, 6, 8},
{10, 5, 7, 2, 4}
}출력:
31
설명:
6 + 7 + 8 + 10 = 31 - 1번째 배열에서 6 선택 (해당 행의 최댓값) - 2번째 배열에서 7 선택 (최댓값인 12를 고르면 이후 행에서 조건을 만족하는 요소를 찾을 수 없음) - 3번째 배열에서 8 선택 (최댓값인 13을 고르면 역시 해답을 구할 수 없음) - 4번째 배열에서 10 선택 (해당 행의 최댓값)
해결 접근 방법
가장 효과적인 접근 방법은 마지막 배열에서 요소를 하나 선택한 뒤, 바로 윗 행으로 올라가면서 현재 선택한 값보다 작은 값 중 가장 큰 값을 찾아 선택하는 것입니다. 이 과정을 첫 번째 행까지 반복하면 됩니다.
단, 이 방법에는 한 가지 예외 상황이 있습니다. i번째 행에 (i+1)번째 행에서 선택한 값보다 작은 요소가 전혀 없는 경우입니다. 이때는 더 이상 진행할 수 없으므로 -1을 반환합니다.
여기에 각 배열을 미리 오름차순으로 정렬해 두면 효율을 크게 높일 수 있습니다. 오름차순으로 정렬하면 가장 큰 요소가 인덱스 m-1에 위치하고, 왼쪽으로 갈수록 값이 작아지므로 조건을 만족하는 가장 큰 요소를 빠르게 찾을 수 있기 때문입니다.
알고리즘
maxSum과 currMax 변수를 초기화합니다.
1단계 − n개의 배열(각 행)을 모두 오름차순으로 정렬합니다.
2단계 − currMax를 마지막 행의 마지막 요소(mat[n-1][m-1])로 설정하고, maxSum에 이 값을 더합니다.
3단계 − i를 n-2부터 0까지 감소시키며 각 행을 순회합니다.
3.1단계 − mat[i][]에서 currMax보다 작은 값 중 가장 큰 요소의 인덱스 j를 찾습니다.
3.2단계 − j가 0보다 작으면, 즉 조건을 만족하는 값이 없다면 -1을 반환합니다.
3.3단계 − currMax를 mat[i][j]로 갱신합니다.
3.4단계 − maxSum에 currMax를 더합니다.
4단계 − 모든 행을 처리한 후 maxSum을 반환합니다.
C++ 구현 예제
위에서 설명한 알고리즘을 실제로 구현한 프로그램입니다.
#include <bits/stdc++.h>
#define M 5
using namespace std;
int calcMaxSumMat(int mat[][M], int n) {
for (int i = 0; i < n; i++)
sort(mat[i], mat[i] + M);
int maxSum = mat[n - 1][M - 1];
int currMax = mat[n - 1][M - 1];
int j;
for (int i = n - 2; i >= 0; i--) {
for (j = M - 1; j >= 0; j--) {
if (mat[i][j] < currMax) {
currMax = mat[i][j];
maxSum += currMax;
break;
}
}
if (j == -1)
return -1;
}
return maxSum;
}
int main() {
int mat[][M] = {
{4, 5, 1, 3, 6},
{5, 9, 2, 7, 12},
{12, 1, 3, 6, 8},
{10, 5, 7, 2, 4}
};
int n = sizeof(mat) / sizeof(mat[0]);
cout << "n개 배열에서 증가하는 순서 요소들의 최대 합: " << calcMaxSumMat(mat, n);
return 0;
}실행 결과
n개 배열에서 증가하는 순서 요소들의 최대 합: 31
이처럼 각 행을 먼저 정렬한 뒤 아래 행부터 위 행으로 거꾸로 탐색하면, 정렬에 O(n·m·log m), 탐색에 O(n·m)이 소요되어 전체적으로 효율적으로 문제를 해결할 수 있습니다.