C++로 최대 합을 가지는 쌍의 개수 구하기

배열이 주어졌을 때, 최대 합(maximum sum)을 가지는 쌍(pair)이 몇 개인지 찾는 문제입니다. 예제를 통해 살펴보겠습니다.

입력

arr = [3, 6, 5, 2, 1, 2, 3, 4, 1, 5]

출력

2

위 배열에서 만들 수 있는 쌍 중 최대 합은 10입니다. 이 합을 가지는 쌍은 총 2개로, 각각 (6, 4)와 (5, 5)입니다.

알고리즘

문제를 해결하는 절차는 다음과 같습니다.

• 임의의 숫자로 배열을 초기화합니다.
• 최대 합 변수를 정수형의 최솟값(INT_MIN)으로 초기화합니다.
• 두 개의 반복문으로 배열을 순회하며 모든 쌍의 합을 계산하고, 그중 최댓값을 구합니다.
• 쌍의 개수를 저장할 카운트 변수를 0으로 초기화합니다.
• 배열을 다시 한 번 두 반복문으로 순회하면서, 현재 쌍의 합이 최대 합과 같으면 카운트를 1씩 증가시킵니다.
• 마지막으로 카운트를 반환합니다.

C++ 구현

다음은 위 알고리즘을 C++로 구현한 코드입니다.

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

int getMaxSumPairsCount(int a[], int n) {
    int maxSum = INT_MIN;
    // 모든 쌍의 합 중 최댓값 찾기
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            maxSum = max(maxSum, a[i] + a[j]);
        }
    }
    // 최대 합과 같은 쌍의 개수 세기
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] + a[j] == maxSum) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    int arr[] = { 3, 6, 5, 2, 1, 2, 3, 4, 1, 5 };
    int n = 10;
    cout << getMaxSumPairsCount(arr, n) << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

2

복잡도 분석

이 알고리즘은 두 번의 이중 반복문을 사용하기 때문에 시간 복잡도는 O(n²)이며, 추가적인 공간 없이 연산만 수행하므로 공간 복잡도는 O(1)입니다.

더 나은 성능이 필요하다면, 배열을 정렬한 뒤 상위 요소들을 활용하는 방식(예: 최대값과 두 번째 최대값의 조합을 먼저 확인)으로 탐색 범위를 줄여 최적화할 수 있습니다.