크기가 N으로 같은 두 개의 배열이 주어졌을 때, 첫 번째 배열에서 X개의 요소를, 두 번째 배열에서 Y개의 요소를 선택하여 얻을 수 있는 최대 합을 구하는 것이 이 문제의 목표입니다.
문제 이해하기
예시를 통해 문제를 자세히 살펴보겠습니다.
입력
arr1 = {1,2,3,4,5} ; X=2
arr2 = {1,3,5,2,7} ; Y=3출력
최대 합 : 24
설명 − arr1에서는 2개, arr2에서는 3개의 숫자를 선택합니다. arr1에서 가장 큰 두 수는 4와 5이고, arr2에서 가장 큰 세 수는 3, 5, 7입니다. 이 다섯 개 요소의 총합은 24이며, 주어진 조건에서 가능한 최댓값입니다.
입력
arr1 = {10,13,16,14} ; X=1
arr2 = {4,1,2,1} ; Y=2출력
최대 합 : 22
설명 − arr1에서는 1개, arr2에서는 2개의 숫자를 선택합니다. arr1에서 가장 큰 수는 16이고, arr2에서 가장 큰 두 수는 4와 2입니다. 이 세 개 요소의 총합은 22로, 조건을 만족하는 최대값입니다.
접근 방법
두 개의 입력 배열 arr1[], arr2[]와 X, Y 값을 받습니다.
두 배열을 오름차순으로 정렬합니다.
정렬된 배열에서 arr1의 마지막 X개 요소와 arr2의 마지막 Y개 요소를 가져옵니다. 오름차순 정렬 기준으로 배열 끝에 위치한 값들이 가장 큰 값들이기 때문입니다.
마지막으로 3번 단계에서 선택한 요소들의 합을 반환하면, 그것이 곧 최대 합이 됩니다.
참고: sort(arr[], int) 함수가 정렬된 배열을 반환한다고 가정합니다.
구현 예제
#include <iostream>
using namespace std;
int max_sum(int arr1[],int arr2[], int length,int X,int Y){
// 배열 정렬
sort(arr1,length);
sort(arr2,length);
int sum=0;
int i;
// arr1의 마지막 X개 요소와 arr2의 마지막 Y개 요소를 더함
for(i=0;i<X;i++){
sum+=arr1[length-i-1];
}
for(i=0;i<Y;i++){
sum+=arr2[length-i-1];
}
return(sum);
}
// 드라이버 프로그램
int main(){
int arr1[]={1,1,1,3,7};
int arr2[]={1,1,2,3,5};
int x=3,y=2;
printf( "첫 번째와 두 번째 배열에서 각각 X개, Y개 요소를 선택했을 때의 최대 합은 %d",max_sum(arr1,arr2,5,x,y));
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
첫 번째와 두 번째 배열에서 각각 X개, Y개 요소를 선택했을 때의 최대 합은 19
정리
이 문제의 핵심은 그리디(Greedy) 알고리즘 사고방식입니다. 각 배열에서 가장 큰 값들을 우선적으로 선택하면 전체 합이 자연스럽게 최대가 됩니다. 시간 복잡도는 배열 정렬이 지배하므로 O(N log N)이며, 정렬 후에는 단순히 뒤에서부터 X개와 Y개를 더하면 되므로 매우 효율적입니다.