[BOJ] 9576 : 책 나눠주기

문제 : https://www.acmicpc.net/problem/9576

---

그리디 그리디알고리즘

[ 알고리즘풀이 ]

 그리디하게 문제를 해결 할 수 있다.

 (a1, b1) (a2, b2) .... (aM, bM) 신청서가 있다고 할 때, b값이 작고 b값이 같다면 a값이 작은 신청서들을 먼저 처리해주면 된다.

 

 1) 주어진 학생들의 신청서(a,b)를 b가 더 작고 b가 같다면 a가 더 작은 순으로 정렬한다.

 2) 정렬된 신청서를 순회하며 a부터 시작해 b까지 빌려줄 수 있는 책을 빌려준다.

 

[ 코드 C++ ]

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int t;
    cin >> t;
    while (t--) {
        int N, M, ans = 0;
        pair<int, int> list[1000];
        bool checked[1001] = {};
 
        cin >> N >> M;
        for (int i = 0; i < M; i++)
            cin >> list[i].second >> list[i].first;
 
        sort(list, list + M);
 
        for (int i = 0; i < M; i++) {
            for(int j = list[i].second; j <= list[i].first; j++)
                if (!checked[j]) {
                    checked[j] = true;
                    break;
                }
        }
 
        for (int i = 1; i <= N; i++)
            if (checked[i]) ans++;
 
        cout << ans << '\n';
 
    }
}

[ github ]

github.com/travelbeeee/ProblemSolving/blob/master/BOJ/BOJ9576.cpp

travelbeeee/ProblemSolving

---