이 튜토리얼에서는 음수를 포함할 수 있는 배열에서 쌍별 곱(pairwise product)의 최대 합을 구하는 프로그램을 C++로 구현하는 방법을 알아보겠습니다.
문제 조건은 다음과 같습니다. 정수로 이루어진 배열이 주어지며, 배열의 원소들을 두 개씩 짝지어 곱한 값들의 합이 최대가 되도록 만들어야 합니다. 각 원소는 정확히 한 번만 짝에 사용될 수 있습니다.
알고리즘 접근 방법
이 문제의 핵심 아이디어는 그리디(Greedy) 접근법입니다. 배열을 먼저 정렬한 뒤 아래 규칙에 따라 원소들을 짝지어 줍니다.
- 배열을 오름차순으로 정렬합니다.
- 음수끼리 짝지으면 곱이 양수가 되므로, 가장 작은 음수(절댓값이 큰 수)부터 차례대로 짝짓는 것이 유리합니다.
- 양수끼리 짝지을 때는 큰 값끼리 곱해야 합이 최대가 되므로, 가장 큰 양수 두 개부터 짝짓습니다.
- 짝을 이루지 못한 원소가 남았다면, 남은 음수와 양수를 곱하거나 해당 값을 그대로 합산합니다.
결과값이 매우 커질 수 있으므로 109+7(Mod)로 나눈 나머지를 구하도록 처리했습니다.
예시 코드
#include <bits/stdc++.h>
#define Mod 1000000007
using namespace std;
//최대 합을 찾는 함수
long long int findSum(int arr[], int n) {
long long int sum = 0;
//배열을 오름차순으로 정렬
sort(arr, arr + n);
int i = 0;
//음수 부분 처리: 작은 음수끼리 짝짓기
while (i < n && arr[i] < 0) {
if (i != n - 1 && arr[i + 1] <= 0) {
sum = (sum + (arr[i] * arr[i + 1]) % Mod) % Mod;
i += 2;
}
else
break;
}
int j = n - 1;
//양수 부분 처리: 큰 양수끼리 짝짓기
while (j >= 0 && arr[j] > 0) {
if (j != 0 && arr[j - 1] > 0) {
sum = (sum + (arr[j] * arr[j - 1]) % Mod) % Mod;
j -= 2;
}
else
break;
}
//남은 원소 처리
if (j > i)
sum = (sum + (arr[i] * arr[j]) % Mod) % Mod;
else if (i == j)
sum = (sum + arr[i]) % Mod;
return sum;
}
int main() {
int arr[] = { -1, 9, 4, 5, -4, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findSum(arr, n);
return 0;
}
출력 결과
87
결과 해석
예제 배열 {-1, 9, 4, 5, -4, 7}을 정렬하면 {-4, -1, 4, 5, 7, 9}가 됩니다. 음수끼리 짝지으면 (-4 × -1) = 4가 되고, 양수는 큰 값끼리 짝지어 (9 × 7) = 63, (5 × 4) = 20이 됩니다. 따라서 최종 합은 4 + 63 + 20 = 87입니다.
마무리
이처럼 정렬과 그리디 기법을 활용하면 시간 복잡도 O(N log N) 안에 음수가 포함된 배열의 쌍별 곱 최대 합을 효율적으로 구할 수 있습니다. 배열 최적화 유형의 코딩 테스트 문제를 풀 때 이 접근 방식을 참고해 보세요.