C++로 쌍 배열에서 최대 K개의 쌍을 선택해 얻을 수 있는 최대 비용 구하기

문제 개요

쌍(pair)으로 이루어진 배열 A가 주어졌을 때, 최대 K개의 쌍을 선택하여 얻을 수 있는 최대 비용을 구하는 문제입니다.

여기서 '비용(cost)'은 다음 두 값의 곱으로 정의됩니다.

• 선택된 모든 쌍의 첫 번째 원소의 합
• 선택된 쌍들 중 두 번째 원소의 최솟값

예를 들어 (4, 8), (10, 3), (3, 6) 세 쌍을 선택했다면 비용은 (4+10+3)×3 = 51이 됩니다(K=3인 경우).

입력 예시

입력이 다음과 같다면,

A = [(15, 5), (65, 25), (35, 20), (20, 5), (35, 20), (15, 18), (3, 8), (12, 17)], K = 4

출력은 2700이 됩니다.

해결 전략

이 문제는 그리디(greedy) 기법과 정렬, 그리고 균형 이진 탐색 트리(std::set)를 조합하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 배열을 두 번째 원소 기준으로 오름차순 정렬한 뒤 뒤에서부터 한 쌍씩 추가합니다. 이렇게 하면 현재 처리 중인 쌍의 두 번째 값이 항상 지금까지 선택된 쌍들 중 최솟값이 됩니다.
• 선택된 쌍의 개수가 K를 초과하면, 첫 번째 원소가 가장 작은 쌍을 제거하여 첫 번째 원소의 합을 최대한 크게 유지합니다.
• 매 단계마다 (현재 합 × 현재 쌍의 두 번째 값)을 계산해 최댓값을 갱신합니다.

알고리즘 단계

1. res := 0, sum := 0으로 초기화합니다.
2. N := A의 크기로 설정합니다.
3. 쌍을 저장할 집합 my_set을 정의합니다.
4. 배열 A를 각 쌍의 두 번째 값을 기준으로 오름차순 정렬합니다.
5. i를 N−1부터 0까지 감소시키며 반복합니다.
   • (A[i]의 첫 번째 원소, i) 쌍을 만들어 my_set에 삽입합니다.
   • sum에 A[i]의 첫 번째 원소를 더합니다.
   • my_set의 크기가 K보다 커지면, 집합에서 가장 작은 원소(첫 번째 원소 기준)를 꺼내 sum에서 빼고 제거합니다.
   • res와 sum × A[i].second 중 더 큰 값으로 res를 갱신합니다.
6. res를 반환합니다.

C++ 구현 예제

아래 코드를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
bool compactor(const pair<int, int>& a, const pair<int, int>& b) {
    return (a.second < b.second);
}
int get_maximum_cost(vector<pair<int, int> > &A, int K){
    int res = 0, sum = 0;
    int N = A.size();
    set<pair<int, int>> my_set;
    sort(A.begin(), A.end(), compactor);
    for (int i = N - 1; i >= 0; --i) {
        my_set.insert(make_pair(A[i].first, i));
        sum += A[i].first;
        while (my_set.size() > K) {
            auto it = my_set.begin();
            sum -= it->first;
            my_set.erase(it);
        }
        res = max(res, sum * A[i].second);
    }
    return res;
}
int main() {
    vector<pair<int, int> > arr = {{15, 5}, {65, 25}, {35, 20}, {20, 5}, {35, 20}, {15, 18}, {3, 8}, {12, 17}};
    int K = 4;
    cout << get_maximum_cost(arr, K);
}

입력

{{15, 5}, {65, 25}, {35, 20}, {20, 5}, {35, 20}, {15, 18}, {3, 8}, {12, 17}}, 4

출력

2700

복잡도 분석

• 시간 복잡도: O(N log N) — 정렬에 O(N log N)이 소요되며, 이후 각 원소마다 set의 삽입·삭제 연산이 O(log N)씩 발생합니다.
• 공간 복잡도: O(K) — set에는 항상 최대 K개의 쌍만 유지됩니다.