C++로 두 배열에서 순서대로 원소를 선택해 최대 합 구하기

이 문제에서는 두 개의 배열 arr1[]과 arr2[], 그리고 두 개의 정수 N과 M이 주어집니다. N은 arr1에서 가져올 수 있는 원소의 최대 개수를, M은 arr2에서 가져올 수 있는 원소의 최대 개수를 의미합니다.

배열의 인덱스를 처음부터 순서대로 탐색하면서 각 인덱스 i마다 arr1[i]와 arr2[i] 중 하나를 선택해야 하며, arr1에서는 최대 N개, arr2에서는 최대 M개까지만 선택할 수 있습니다. 이렇게 선택한 원소들의 합이 최대가 되도록 만드는 것이 목표입니다.

즉, 우리가 작성해야 할 것은 순서대로 두 배열에서 원소를 선택하여 최대 합을 구하는 C++ 프로그램입니다.

문제 이해를 위한 예시

입력

arr1[] = {5, 1, 6, 2, 8, 9}
arr2[] = {8, 4, 7, 9, 1, 3}
N = 3, M = 2

출력

28

설명

i = 0 : arr1[0] = 5, arr2[0] = 8 → 8 선택 (arr2)
i = 1 : arr1[1] = 1, arr2[1] = 4 → 4 선택 (arr2)
i = 2 : arr1[2] = 6, arr2[2] = 7 → 6 선택 (arr1)
i = 3 : arr1[3] = 2, arr2[3] = 9 → 2 선택 (arr1)
i = 4 : arr1[4] = 8, arr2[4] = 1 → 8 선택 (arr1)

maxSum = 8 + 4 + 6 + 2 + 8 = 28

인덱스 2와 3에서 arr2의 값이 더 크지만, arr2에서 선택할 수 있는 개수(M = 2)를 이미 모두 사용했기 때문에 arr1의 값을 선택하게 됩니다.

풀이 접근 방식

이 문제는 그리디(greedy) 기법으로 해결할 수 있습니다. 배열의 처음부터 끝까지 순서대로 탐색하면서, 각 인덱스에서 두 값 중 더 큰 값을 선택하되 해당 배열의 선택 가능 횟수(할당량)가 남아 있을 때만 선택하는 방식입니다.

예를 들어 arr1[i]가 arr2[i]보다 크고 arr1의 남은 선택 횟수 N이 0보다 크면 arr1[i]를 더한 뒤 N을 1 감소시킵니다. 반대로 arr2[i]가 더 크거나 같고 M이 남아 있으면 arr2[i]를 선택합니다. 만약 더 큰 값이 속한 배열의 할당량이 소진되었다면, 남은 할당량이 있는 다른 배열의 값을 선택하고, 두 할당량이 모두 소진되면 탐색을 종료한 후 지금까지의 합을 반환합니다.

알고리즘

초기화:

maxSum = 0

1단계: 인덱스 i를 0부터 n-1까지 순회합니다.

1.1단계: arr1[i] > arr2[i]이고 N > 0이면 → maxSum에 arr1[i]를 더하고 N을 1 감소시킵니다.

1.2단계: 그렇지 않고 arr1[i] <= arr2[i]이고 M > 0이면 → maxSum에 arr2[i]를 더하고 M을 1 감소시킵니다.

1.3단계: 그렇지 않고 M > 0이면 → maxSum에 arr2[i]를 더하고 M을 1 감소시킵니다.

1.4단계: 그렇지 않고 N > 0이면 → maxSum에 arr1[i]를 더하고 N을 1 감소시킵니다.

1.5단계: 어느 조건에도 해당하지 않으면(두 할당량 모두 소진) 반복을 종료합니다.

2단계: maxSum을 반환합니다.

예제 코드

다음은 위 풀이의 동작을 보여주는 C++ 프로그램입니다.

#include<iostream>
using namespace std;

int calcMaxSumFromArrays(int arr1[], int arr2[], int N, int M, int size1, int size2) {
    int maxSum = 0;
    for(int i = 0; i < size1; i++){
        if(arr1[i] > arr2[i] && N > 0){
            maxSum += arr1[i];
            N--;
        }
        else if(arr1[i] <= arr2[i] && M > 0){
            maxSum += arr2[i];
            M--;
        }
        else if(M > 0){
            maxSum += arr2[i];
            M--;
        }
        else if(N > 0){
            maxSum += arr1[i];
            N--;
        }
        else
            return maxSum;
    }
    return maxSum;
}

int main() {
    int arr1[] = {5, 1, 6, 2, 8, 9};
    int arr2[] = {8, 4, 7, 9, 1, 3};
    int N = 3, M = 2;
    int size1 = sizeof(arr1)/sizeof(arr1[0]);
    int size2 = sizeof(arr2)/sizeof(arr2[0]);
    cout<<"순서대로 두 배열에서 원소를 선택하여 얻을 수 있는 최대 합은 "
        <<calcMaxSumFromArrays(arr1, arr2, N, M, size1, size2);
    return 0;
}

출력

순서대로 두 배열에서 원소를 선택하여 얻을 수 있는 최대 합은 28

이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 별도의 추가 공간을 사용하지 않으므로 공간 복잡도는 O(1)입니다.