BOJ 25391 : 특별상

• 문제 링크 : boj.kr/25391
• 난이도 : G5
• 태그 : 그리디, 정렬

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

bool comp(pll &a, pll &b) {
    if(a.second == b.second) {
        return a.first < b.first;
    }
    return a.second > b.second;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    ll n, m, k;
    cin >> n >> m >> k;
    vector<pll> arr(n);
    for(auto &u : arr) cin >> u.first >> u.second;

    ll ans = 0;
    sort(all(arr), comp);
    for(int i = 0; i < k; i++) {
        ans += arr[i].first;
    }
    vector<ll> arr2(n-k);
    for(int i = 0; i < n-k; i++) {
        arr2[i] = arr[i+k].first;
    }
    sort(all(arr2), greater<ll>());

    for(int i = 0; i < m; i++) {
        ans += arr2[i];
    }
    cout << ans;
    return 0;
}

---

풀이

심판의 점수를 기준으로 정렬한 뒤 k명을 뽑아 본상을 수여한다.

이후 본상 수상자를 제외한 인원을 주최자의 점수로 정렬한 뒤 m명을 뽑아 특별상을 수여한다.

본상 수상자가 아닌 인원에서 특별상을 수여하는 것이 이득임은 다음처럼 보일 수 있다.

본상 수상자에게 특별상을 수상하게 된다면 심판의 점수를 기준으로 정렬했을 때, K+1번째 참여자가 본상 인원에 포함된다. K+1번째 수상자에게 주최자가 수여한 점수가 본상 수상자를 제외한 인원을 주최자의 점수로 정렬했을 때 m번째에 들지 못하면 결론적으로 손해가 된다.