[백준 9576번] [그리디] 책 나눠주기

사실 이 문제는 백준 19580번 "마스크가 필요해"와 완전히 접근방법이 동일하다.

viyoung.tistory.com/171

[백준 19580번] [그리디/ 우선순위 큐] 마스크가 필요해

왜냐하면, 9676번과 19580문제에서 가장 Tight하게 해당 value를 만족하는 것을 선택한다는 핵샘이 동일하기 때문이다.

 

이전 19580문제 해설에서 언급한 것처럼

책을 가질 수 있는 scope를 increasing order로 정렬하고, 책 또한 번호를 증가시켜가면서 책을 가질 수 있는 후보가 될 수 있는지를 체크해주면 된다. 책을 가질 수 있는 후보 중 가장 tight하게 만족하는 것을 골라주면 된다.

추가적으로 pq에 넣은 것들은 책 번호가 계속 증가하고 있는 상황이므로 각 개인의 책 scope의 하한선을 책 번호가 무조건 넘게 된다. 따라서 상한선 밑에 책 번호가 존재하는지만 판단해주면 된다.

 

따라서 이 문제 또한 O(nlgn)에 처리할 수 있게 된다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
typedef pair<int, int> pii;

struct compare{
    bool operator()(const pii &value1, const pii &value2){
        return value1.second> value2.second;
    }
};

int main(void){
    fastio;
    int t;
    cin >> t;

    for(int i = 0; i < t; i++){
        priority_queue<pii, vector<pii>, greater<pii> > pq;
        int n, m;
        cin >> n >> m;
        for(int j = 0; j < m; j++){
            int temp1, temp2;
            cin >> temp1 >> temp2;
            pq.push(make_pair(temp1, temp2));
        }
        priority_queue<pii, vector<pii>, compare> check_pq;
        int result = 0;
        for(int j = 1; j <= n; j++){
            while(!pq.empty()){
                pii check = pq.top(); pq.pop();
                if(check.first <= j && j <= check.second){
                    check_pq.push(check);
                }
                else{
                    pq.push(check);
                    break;
                }
            }
            while(!check_pq.empty()){
                pii booked = check_pq.top(); check_pq.pop();
                if(j <= booked.second){
                    result += 1;
                    break;
                }
            }
        }
        cout << result << "\n";
    }

    return 0;
}