C++로 주어진 배열에서 최대 nCr 값을 만드는 쌍 찾기

문제 개요

n개의 양의 정수로 구성된 배열 arr[]가 주어졌을 때, 조합 값 arr[i]Carr[j]가 가능한 한 최대가 되도록 만드는 두 원소 arr[i]와 arr[j]를 찾는 것이 목표입니다. 조건을 만족하는 쌍이 여러 개 존재하는 경우에는 그중 하나만 출력하면 됩니다.

입력 예시:

arr[] = {4, 1, 2}

출력 예시:

4 2

배열에서 만들 수 있는 조합 값을 하나씩 살펴보면 다음과 같습니다.

⁴C₁ = 4 → 쌍 (4, 1)
⁴C₂ = 6 → 쌍 (4, 2)
²C₁ = 2 → 쌍 (1, 2)

세 경우를 비교했을 때 ⁴C₂가 가장 크므로, 최대 nCr 값을 갖는 쌍은 (4, 2)입니다.

접근 방법

ⁿC_r은 고정된 r에 대해 n이 커질수록 단조 증가하는 함수입니다. 즉, ⁿ⁺¹C_r > ⁿC_r가 항상 성립합니다. 이 성질을 활용하면 배열의 모든 원소 중 가장 큰 값을 n으로 선택하는 것이 유리하다는 결론에 도달할 수 있으며, 이렇게 하면 n의 값이 고정됩니다.

이제 남은 문제는 r을 선택하는 것입니다. ⁿC_r = ⁿC_n-r이라는 대칭성 때문에, nCr의 값은 r = n/2 지점을 기준으로 먼저 최댓값에 도달한 후 다시 감소합니다.

n이 홀수인 경우: 최댓값은 r = n/2와 r = n/2 + 1 두 지점에서 발생합니다. 예를 들어 n = 11일 때는 ¹¹C₅와 ¹¹C₆에서 최대가 됩니다.
n이 짝수인 경우: 최댓값은 r = n/2에서 발생합니다. 예를 들어 n = 4일 때는 ⁴C₂에서 최대가 됩니다.

결국 알고리즘은 다음 세 단계로 요약할 수 있습니다.

배열을 오름차순으로 정렬합니다.
가장 큰 원소를 n으로 고정합니다.
나머지 원소 중 n/2에 가장 가까운 값을 r로 선택합니다.

C++ 구현 예제

// C++로 구현한 풀이
#include <bits/stdc++.h>
using namespace std;

// 최대 nCr을 만드는 쌍을 출력하는 함수
void printMaxValPair1(vector<long long>& v1, int n1){
    sort(v1.begin(), v1.end());
    // nCr에서 n에 해당하는 값
    long long N1 = v1[n1 - 1];
    // 경우 1 : N1이 홀수일 때
    if (N1 % 2 == 1) {
        long long first_maxima1 = N1 / 2;
        long long second_maxima1 = first_maxima1 + 1;
        long long ans1 = 3e18, ans2 = 3e18;
        long long from_left1 = -1, from_right1 = -1;
        long long from = -1;
        for (long long i = 0; i < n1; ++i) {
            if (v1[i] > first_maxima1) {
                from = i;
                break;
            }
            else {
                long long diff = first_maxima1 - v1[i];
                if (diff < ans1) {
                    ans1 = diff;
                    from_left1 = v1[i];
                }
            }
        }
        from_right1 = v1[from];
        long long diff1 = first_maxima1 - from_left1;
        long long diff2 = from_right1 - second_maxima1;
        if (diff1 < diff2)
            cout << N1 << " " << from_left1;
        else
            cout << N1 << " " << from_right1;
    }
    // 경우 2 : N1이 짝수일 때
    else {
        long long maxima = N1 / 2;
        long long ans1 = 3e18;
        long long R = -1;
        for (long long i = 0; i < n1 - 1; ++i) {
            long long diff = abs(v1[i] - maxima);
            if (diff < ans1) {
                ans1 = diff;
                R = v1[i];
            }
        }
        cout << N1 << " " << R;
    }
}

// 드라이버 코드
int main(){
    vector<long long> v1 = { 1, 1, 2, 3, 6, 1 };
    int n1 = v1.size();
    printMaxValPair1(v1, n1);
    return 0;
}

실행 결과

6 3

위 코드에서 가장 큰 값은 6이므로 n = 6으로 고정됩니다. 이후 나머지 원소 {1, 1, 1, 2, 3} 중에서 6 ÷ 2 = 3에 가장 가까운 값 3이 r로 선택되어 (6, 3) 쌍이 출력됩니다. 실제로 ⁶C₃ = 20으로, 이 배열에서 만들 수 있는 조합 중 가장 큰 값입니다.

정렬에 O(n log n), 최적의 r 탐색에 O(n)이 소요되므로 전체 시간 복잡도는 O(n log n)이며, 추가 공간 복잡도는 O(1)입니다.