[백준] 17364번 대회

17364 대회

문제

---

형섭이는 세계에서 고작 K번째로 프로그래밍을 잘하지만, 최대한 많은 프로그래밍 대회에서 우승하여 자신의 이름을 알리고 싶어한다. 형섭이가 프로그래밍 대회에 참가하면 자기보다 잘하는 사람에게는 항상 지고 자기보다 못하는 사람은 항상 이긴다. 즉, 형섭이가 프로그래밍 대회에서 우승하려면 형섭이보다 잘하는 사람이 대회에 참가하지 않아야 하며 그런 대회에서는 형섭이가 항상 우승한다.

전세계에서는 총 N개의 프로그래밍 대회가 개최되며 각 대회는 Si일차부터 Ei일차까지 열린다. 대회가 열리는 장소가 다르므로 어느 누구라도 기간이 겹치는 대회는 동시에 참가할 수 없다. 형섭이는 자기보다 잘하는 K-1명의 사람들이 어떤 대회에 참가하는지 미리 알 수 있다. 형섭이는 K-1명이 참가하지 않는 대회들을 골라 최대한 많이 우승할 수 있도록 대회에 참가할 것이다.

만약 K-1명의 사람들이 적절하게 대회에 참가한다면 형섭이가 우승할 수 있는 대회가 얼마 없을 것이다. 형섭이는 그런 경우에 자신이 최대 몇 개의 대회에서 우승할 수 있는지 살펴보고자 한다. 대회의 정보가 주어질 때 형섭이가 우승할 수 있는 대회의 수를 구하는 프로그램을 작성하여라.

입력

---

첫 번째 줄에는 대회의 수 N (1 ≤ N ≤ 100,000), 형섭이의 등수 K (1 ≤ K ≤ 100,000)가 주어진다.

두 번째 줄부터 N개의 줄에는 대회의 시작 날짜 Si, 종료 날짜 Ei가 주어진다. (1 ≤ Si, Ei ≤ 1,000,000,000)

출력

---

형섭이가 우승할 수 있는 최대 대회 수가 가장 적어지도록 K-1명이 대회에 적절히 참가할 때, 형섭이가 우승할 수 있는 대회 수를 출력한다.

---

풀이)

어려워서 다른 분 풀이 도움을 받은 문제이다.

vector로 일일히 정렬해서 풀기엔 시간이 오래 걸려서

mutiset을 이용해서 푸는 문제이다.

(mutiset : set과 달리 중복 원소를 허락해서 set에서 의미없던 lower_bound(), upper_bound(), equal()을 유용하게 사용가능)

과정은 이러하다.

일단 두개의 multiset 자료형을 선언한다.

multiset <pair<int,int>> test;    //대회들을 저장하는 multiset

multiset <int> person;    //k-1명이 참가한 대회들이 끝나는 날을 저장하는 multiset

1. 대회들을 multiset test에 저장해, 일찍 끝나는 순으로 정렬해 놓는다.

2. test에 저장된 첫번째 대회부터 마지막 대회까지 둘러본다.

 2.1. i번째 대회 형섭이 참여 가능x

      만약, i번째 대회가 형섭이가 다른 대회에 참가해서 못 참가할 대회라면 굳이 다른 사람들도 참가할 필요 없으니깐 pass

 

 2.2. i번째 대회 형섭이 참여 가능o

   2.2.1.다른 k-1명 중 단 한 명도 다른 대회에 참가하지 않았다면 그 대회에 참가해 형섭이가 참가하지 못하도록 방해

    person.insert(i번째 대회 끝나는 날)

   2.2.2. 기존에 대회 참가한 k-1명 혹은 k-1명 사람 일부의 끝나는 날을 확인 

    i번째 대회의 시작일과 다른 k-1명이 참가한 대회의 끝나는 날을 lower_bound()를 이용해 확인

    auto it = person.lower_bound(i번째 대회의 시작일) 

    => i번째 대회 시작일보다 같거나 큰 (k-1 명 사람들이 참여한 대회) 끝나는 날 반복자 리턴

         기존 사람들 중 i번째 대회에 참가할 수 있는 사람이 있을 경우(그 사람이 끝나는 날이 i번째 시험 끝나는 날보다 빠른 경우)

         그 사람을 참가시켜 형섭이가 참가하지 못하도록 방해

    person.insert(i번째 대회 끝나는 날)

   2.2.3. 기존에 참가했던 다른 사람들이 또 참가하는 건 불가능하지만, 

k-1명 중 남는 사람이 있다면 i번째 대회 참가시켜서 형섭이가 참가하지 못하도록 방해

   2.2.4. 위의 2.2.1~2.2.3에 해당하는 경우들이 없다면 어쩔 수 없이 형섭이가 i번째 대회에 참가

설명이 복잡한데, 코드를 한 줄씩 디버깅 하면 이해 가능할 것이다.   

코드)

#include <stdio.h>
#include <algorithm>
#include <set>
using namespace std;
 
struct Myorder {
    bool operator()(const pair<int, int>&a, const pair<int, int>&b) {
        if (a.second == b.second) {
            return a.first < b.first;
        }
        else {
            return a.second < b.second;
        }
    }
};
int N, K;
//mutiset 중복가능. set에서 의미없던 lower_bound(), upper_bound(),equal() 유용하게 사용
multiset < pair<int, int>, Myorder> test;
multiset<int> person;
 
int main() {
    scanf("%d %d", &N, &K);
 
    for (int i = 0; i < N; i++) {
        int s, e;
        scanf("%d %d", &s, &e);
        test.insert({ s,e });//일찍 끝나는 순으로 정렬
    }
    
    int cnt = 0;//형섭이가 참가하는 대회 개수
    int c_end = 0;//형섭이가 대회 끝나는 날
 
    for (auto i:test) {
        if (i.first <= c_end) {//어차피 i번째 시험에 형섭이는 참여 못함. 굳이 k-1명 중에서도 참가 안해도됨
            continue;
        }
        if (K > 1 && person.empty()) {//k-1명중 한 명이 무조건 시험볼 수 있을 때
            person.insert(i.second);
            continue;
        }
        //(i번째 시험 시작일 <= k-1명 혹은 일부들이 시험끝나는날) 반복자 확인
        auto it = person.lower_bound(i.first); 
        if (it != person.begin()) { //k-1명중 이 대회를 참가할 수 있는 사람이 있다면?
            it--;//i번째 시험을 볼 수 있는 k-1명 중 한사람이 끝나는 날(가장 늦게 끝난 사람이 i번째 시험 참여)
            person.erase(it);
            person.insert(i.second);
        }
        else {
            if (person.size() < K - 1) {//K-1명 중 남아 있는 한 명이 시험 볼 수 있음
                person.insert(i.second);
            }
            else { //k-1명이 모두 다른 시험을 보는 중이라 형섭이가 시험 봄
                cnt++;
                c_end = i.second;
            }
        }
    }
    printf("%d", cnt);
    return 0;
}