[C++] BOJ-9576

 

 

문제풀이

---

1. pair<int,int>형 배열변수에 신청서 정보를 넣고 bool 형 배열변수를 선언한다.

 

2. pair변수의 second의 크기에 따라 오름차순으로 정렬하되 만약 second의 크기가 같다면 first크기에 따라 내림차순으로 정렬을 해야한다. (그리디하게 문제를 해결해야 함)

 

3. 그 후 반복문을 통해서 만약 book 배열에 false로 남아있는 책 중 하나라도 학생이 원하는 책이 false라면 그 책을 true로 바꿔주고 다음 학생의 신청서로 넘어간다.

 

p.s) 이 문제는 사실 정당성 증명을 하진 못했다. 그냥 뭔가 직관적으로 떠올라서 (왠지 이런 원리일 것 같은데..?) 그대로 구현해보니 정답이 떴다.

 

 

45분

#include <iostream>
#include <algorithm>
 
using namespace std;
 
bool cmp(pair<int,int> a, pair<int,int> b){
    if(a.second == b.second){
        return a.first > b.first;
    }
    return a.second < b.second;
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int T;
    cin >> T;
    
    for(int test = 0; test<T; test++){
        int N, M, cnt = 0;
 
        cin >> N >> M;
        pair<int,int> student[M];
        bool book[N+1] = {};
        
        for(int i = 0; i<M; i++){
            cin >> student[i].first >> student[i].second;
        }
        
        sort(student,student+M, cmp);
        
        for(int i = 0; i<M; i++){
            for(int j = student[i].first; j<=student[i].second; j++){
                if(book[j] == 0){
                    book[j] = true;
                    cnt++;
                    break;
                }
            }
        }
        cout << cnt << "\n";
    }
}