C++로 N개의 숫자를 N/2쌍으로 묶어 제곱의 합 최소화하는 방법

문제 개요

n개의 원소로 이루어진 배열이 주어집니다. 이 배열의 원소들을 n/2개의 쌍으로 묶되, 각 쌍에 속한 두 수의 합을 제곱한 값들의 총합이 최소가 되도록 만드는 것이 이번 문제의 목표입니다.

예시

다음과 같은 배열이 주어졌다고 가정해 보겠습니다.

arr[] = {5, 10, 7, 4}

배열을 (4, 10)과 (5, 7) 두 쌍으로 묶으면 최소 제곱합은 340이 됩니다.

(4 + 10)² + (5 + 7)² = 14² + 12² = 196 + 144 = 340

접근 방식: 왜 '작은 수 + 큰 수' 조합일까?

(a + b)²는 두 수가 모두 클수록 값이 급격하게 커집니다. 따라서 큰 수끼리 한 쌍을 이루면 전체 합이 불필요하게 커지게 됩니다. 이를 피하려면 정렬된 배열에서 가장 작은 수와 가장 큰 수를 서로 짝지어 주는 그리디(greedy) 전략이 효과적입니다.

실제로 위 예시에서 큰 수끼리 묶는 (7, 10), (4, 5) 조합의 제곱합은 289 + 81 = 370으로, 양 끝값끼리 묶는 방식(340)보다 더 큽니다.

알고리즘 단계

1. 배열을 오름차순으로 정렬합니다.
2. 배열의 시작 인덱스(start)와 끝 인덱스(end)를 가리키는 두 변수를 준비합니다.
3. 두 포인터가 가리키는 원소의 합을 구한 뒤 제곱합니다.
   sum = arr[start] + arr[end];
   sum = sum * sum;
4. start < end를 만족하는 동안 위 과정을 반복하며 minSum에 누적하고, start는 증가, end는 감소시킵니다.

정렬에 O(n log n), 페어링에 O(n)이 소요되므로 전체 시간 복잡도는 O(n log n)입니다.

C++ 구현 예제

#include <iostream>
#include <algorithm>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;

int getMinSquareSum(int *arr, int n) {
    sort(arr, arr + n);          // 1. 배열 정렬
    int minSum = 0;
    int start = 0;
    int end = n - 1;
    while (start < end) {        // 2. 양 끝에서 안쪽으로 이동
        int sum = arr[start] + arr[end];
        sum *= sum;              // 3. 합의 제곱 계산
        minSum += sum;           // 4. 결과 누적
        ++start;
        --end;
    }
    return minSum;
}

int main() {
    int arr[] = {5, 10, 7, 4};
    int res = getMinSquareSum(arr, SIZE(arr));
    cout << "Minimum square sum: " << res << "\n";
    return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 출력이 생성됩니다.

Minimum square sum: 340