책 나눠주기 (feat. 백준, 9576번)

책 나눠주기
https://www.acmicpc.net/problem/9576

9576번: 책 나눠주기

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct cmp {
    bool operator()(const pair<int, int>& v1, const pair<int, int>& v2) const{
        if(v1.second == v2.second)
            return v1.first > v2.first;
        return v1.second > v2.second;
    }      
};
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    bool visit[1001];
    register int T;
    cin >> T;
    for(register int t = 0, N, M, cnt; t < T; ++t){
        cin >> N >> M;
        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> q;
        for(register int m = 0, a, b; m < M; ++m)
            cin >> a >> b, q.push(make_pair(a, b));
        memset(visit, false, N + 1);
        cnt = 0;
        while(!q.empty()){
            auto p = q.top(); q.pop();
            register int a = p.first, b = p.second;
            for(register int i = a; i <= b; ++i)
                if(!visit[i]){
                    visit[i] = true;
                    ++cnt;
                    break;
                }
        }
        cout << cnt << "\n";
    }
    return 0;
}
// *&)*@*

 

1. 입력받은 범위를 정렬하여 그 순서대로 N개의 배열에 방문 표시를 해주는 방식입니다.
2. 결국 정렬이 관건인데, 정렬할 기준은 cmp를 참고하시면 됩니다.
   - End가 더 큰 값으로 내림차순
   - End가 같다면 Start가 더 큰 값으로 내림차순