C++로 두 배열의 곱셈 합 최댓값 구하기

이 문제에서는 크기가 n인 두 배열 arr1[]과 arr2[]가 주어지며, 우리의 목표는 두 배열의 곱(product)의 합 중 최댓값을 구하는 프로그램을 작성하는 것입니다.

문제 설명

두 배열의 곱의 최대 합(Maximum Sum of Products)을 구해야 합니다. 즉, arr1의 한 원소와 arr2의 한 원소를 짝지어 곱한 뒤, 이러한 곱들의 합이 가장 커지도록 배열의 원소들을 매칭해야 합니다.

예제로 문제 이해하기

입력

arr1[] = {3, 5, 6}
arr2[] = {1, 4, 2}

출력

37

설명

곱의 최대 합: 6*4 + 5*2 + 3*1 = 24 + 10 + 3 = 37

해결 접근 방식

단순한 방법: arr1과 arr2의 모든 원소 쌍을 조합해 가능한 모든 경우의 합을 계산하고, 그중 최댓값을 반환하는 것입니다. 하지만 이 방법은 시간 복잡도가 높아 비효율적입니다.

효율적인 방법: 두 배열에서 가장 큰 값끼리 서로 곱하면 전체 합이 최대가 된다는 성질을 활용하는 것입니다. 가장 간단한 구현 방법은 두 배열을 모두 내림차순으로 정렬한 뒤, 인덱스 0부터 n-1까지 같은 위치의 원소들을 곱하여 모두 더하는 것입니다.

정렬에 O(n log n)의 시간이 걸리고, 이후의 곱셈 및 합산은 O(n)이므로 전체 시간 복잡도는 O(n log n)입니다.

구현 예제

다음은 위 해결 방법의 동작을 보여주는 C++ 프로그램입니다.

#include<bits/stdc++.h>
using namespace std;

int calcMaxSumOfProd(int arr1[], int arr2[], int n){
    int maxSum = 0;
    sort(arr1, arr1 + n, greater<int>());
    sort(arr2, arr2 + n, greater<int>());
    for (int i = 0; i < n; i++)
    maxSum += (arr1[i] * arr2[i]);
    return maxSum;
}

int main() {
    int arr1[] = { 3, 5, 6 };
    int arr2[] = { 1, 4, 2 };
    int n = sizeof(arr1)/sizeof(arr1[0]);
    cout<<"두 배열의 곱의 최대 합은 "<<calcMaxSumOfProd(arr1, arr2, n);
    return 0;
}

출력 결과

두 배열의 곱의 최대 합은 37

마무리

이처럼 두 배열을 내림차순으로 정렬한 뒤 같은 인덱스의 원소끼리 곱해 더하면, 곱의 합이 최대가 됨을 보장할 수 있습니다. 탐욕(Greedy) 알고리즘의 대표적인 예시로, 정렬만으로 최적해를 얻을 수 있는 간단하면서도 효율적인 문제입니다.