문제 개요
이 문제에서는 n개의 정수로 이루어진 배열 arr[]가 주어지며, 배열에는 음수도 포함될 수 있습니다. 목표는 배열의 원소들을 짝지어 만들 수 있는 쌍별 곱(pairwise product)의 합 중 최댓값을 구하는 프로그램을 작성하는 것입니다.
문제 설명
배열의 원소들을 서로 쌍(pair)으로 묶고, 각 쌍에 속한 두 원소의 곱을 모두 더했을 때 그 합이 최대가 되도록 쌍을 구성해야 합니다.
예제로 이해하기
입력:
arr[] = {-5, 2, 3, 7, -1, 1, -3, 12}
출력:
104
설명:
선택된 쌍: (-5, -3), (2, 3), (-1, 1), (7, 12) 곱의 합 = (-5 × -3) + (2 × 3) + (-1 × 1) + (7 × 12) = 15 + 6 - 1 + 84 = 104
해결 접근 방식
쌍별 곱의 합을 최대화하려면 부호가 같은 값끼리 짝지어야 합니다. 음수끼리 곱하면 양수가 되고, 절댓값이 큰 양수끼리 곱할수록 더 큰 값을 얻을 수 있기 때문입니다. 이러한 짝짓기를 쉽게 하려면 먼저 배열을 오름차순으로 정렬한 뒤, 음수끼리 그리고 양수끼리 차례로 쌍을 만들면 됩니다.
마지막으로 남은 원소가 있는지 확인합니다. 양수 또는 음수가 하나만 남았다면 그 값을 결과에 더하고, 양수와 음수가 하나씩 남았다면 두 값의 곱을 결과에 더합니다.
알고리즘
초기화:
maxSum = 0
1단계: 배열 arr[]을 정렬합니다.
2단계: 배열의 음수 값들을 순회하며 쌍을 만들고, 각 쌍의 곱을 maxSum에 더합니다.
3단계: 배열의 양수 값들을 순회하며 쌍을 만들고, 각 쌍의 곱을 maxSum에 더합니다.
4단계: 마지막으로 남은 값들을 확인합니다.
4-1단계: 양수가 하나 남았다면 그 값을 maxSum에 더합니다.
4-2단계: 음수가 하나 남았다면 그 값을 maxSum에 더합니다.
4-3단계: 양수와 음수가 하나씩 남았다면 두 값의 곱을 maxSum에 더합니다.
5단계: maxSum을 반환합니다.
C++ 구현 예제
아래 프로그램은 위에서 설명한 풀이 과정을 실제로 구현한 것입니다.
#include <bits/stdc++.h>
using namespace std;
long calcSumPairProd(int arr[], int n) {
long maxSum = 0;
sort(arr, arr + n);
int i = 0, j = (n - 1);
while (i < n && arr[i] < 0) {
if (i != n - 1 && arr[i + 1] <= 0) {
maxSum = (maxSum + (arr[i] * arr[i + 1]));
i += 2;
}
else
break;
}
while (j >= 0 && arr[j] > 0) {
if (j != 0 && arr[j - 1] > 0) {
maxSum = (maxSum + (arr[j] * arr[j - 1]));
j -= 2;
}
else
break;
}
if (j > i)
maxSum = (maxSum + (arr[i] * arr[j]));
else if (i == j)
maxSum = (maxSum + arr[i]);
return maxSum;
}
int main() {
int arr[] = { -5, 2, 3, 7, -1, 1, -3, 12 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"배열에서 쌍별 곱의 최대 합은 "<<calcSumPairProd(arr, n);
return 0;
}
실행 결과
배열에서 쌍별 곱의 최대 합은 104
복잡도 분석
배열 정렬에 O(n log n), 정렬된 배열의 순회에 O(n)의 시간이 소요되므로 전체 시간 복잡도는 O(n log n)입니다. 입력 배열을 제자리(in-place)에서 정렬해 사용하므로 추가 공간이 필요 없으며, 공간 복잡도는 O(1)입니다.