C++ – N개의 배열에서 증가하는 순서 요소의 최대 합 구하기

이 튜토리얼에서는 N개의 배열에서 증가하는 순서 요소들의 최대 합을 찾는 프로그램을 다룹니다.

크기가 M인 N개의 배열이 주어졌을 때, 각 배열에서 하나의 요소를 선택해 합을 구하되, 앞선 배열에서 선택한 요소가 뒤따르는 배열에서 선택한 요소보다 반드시 작아야 한다는 조건이 있습니다. 이 조건을 만족하면서 얻을 수 있는 최대 합을 구하는 것이 목표입니다.

접근 방법

이 문제는 그리디(Greedy) 기법으로 효율적으로 해결할 수 있습니다.

1. 모든 배열을 오름차순으로 정렬합니다.
2. 마지막 배열의 최댓값을 합계의 시작점으로 설정합니다.
3. 바로 앞 배열의 뒤쪽(큰 값)부터 역순으로 탐색하며, 직전에 선택한 값보다 작은 첫 번째 요소를 찾습니다.
4. 조건을 만족하는 요소를 찾으면 합계에 더하고, 끝까지 찾지 못하면 유효한 선택이 불가능하므로 0을 반환합니다.

예제 코드

#include <bits/stdc++.h>
#define M 4
using namespace std;
// 각 배열에서 하나의 요소를 선택하여
// 최대 합을 계산하는 함수
int maximumSum(int a[][M], int n) {
    for (int i = 0; i < n; i++)
        sort(a[i], a[i] + M);
    int sum = a[n - 1][M - 1];
    int prev = a[n - 1][M - 1];
    int i, j;
    for (i = n - 2; i >= 0; i--) {
        for (j = M - 1; j >= 0; j--) {
            if (a[i][j] < prev) {
                prev = a[i][j];
                sum += prev;
                break;
            }
        }
        if (j == -1)
            return 0;
    }
    return sum;
}
int main() {
    int arr[][M] = {
        {1, 7, 3, 4},
        {4, 2, 5, 1},
        {9, 5, 1, 8}
    };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maximumSum(arr, n);
return 0;
}

출력

18

동작 원리

위 예제에서 세 개의 배열은 정렬 후 각각 {1, 3, 4, 7}, {1, 2, 4, 5}, {1, 5, 8, 9}가 됩니다. 먼저 마지막 배열에서 최댓값 9를 선택하고, 두 번째 배열에서 9보다 작은 값 중 가장 큰 5를, 첫 번째 배열에서 5보다 작은 값 중 가장 큰 4를 선택합니다. 따라서 최종 합은 9 + 5 + 4 = 18이 됩니다.

시간 복잡도

정렬 단계에서 O(N × M log M), 요소 선택 단계에서 O(N × M)의 시간이 소요되므로 전체 시간 복잡도는 O(N × M log M)입니다.