백준 9576번 책 나눠주기

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

9576번: 책 나눠주기

문제

백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 정수 번호를 중복되지 않게 매겨 두었다.

조사를 해 보니 책을 원하는 서강대학교 학부생이 총 M명이었다. 백준이는 이 M명에게 신청서에 두 정수 a, b (1 ≤ a ≤ b ≤ N)를 적어 내라고 했다. 그러면 백준이는 책 번호가 a 이상 b 이하인 책 중 남아있는 책 한 권을 골라 그 학생에게 준다. 만약 a번부터 b번까지의 모든 책을 이미 다른 학생에게 주고 없다면 그 학생에게는 책을 주지 않는다.

백준이가 책을 줄 수 있는 최대 학생 수를 구하시오.

입력

첫째 줄에 테스트 케이스의 수가 주어진다.

각 케이스의 첫 줄에 정수 N(1 ≤ N ≤ 1,000)과 M(1 ≤ M ≤ 1,000)이 주어진다. 다음 줄부터 M개의 줄에는 각각 정수 ai, bi가 주어진다. (1 ≤ ai ≤ bi ≤ N)

출력

백준이가 책을 줄 수 있는 최대 학생 수를 출력한다.

-----------------------------------------------------------------------------------------------------------------------------------

풀이

이분 매칭 으로 푸는 방법도 있지만  이분 매칭은 나중에 포스팅하고 그리디로 먼저 풀이하겠다.

그리디 대부분 문제가 그렇듯이 정렬을 해주었다.  처음에 책 정렬을 잘못하여 진짜 엄청나게 Fail 받았다. ㅜㅜ

처음에 만든 조건은 책 시작번호 가 작은 값이 앞에 오게 해 주고 만약 책 시작 번호가 같다면 책 끝나는 번호가 앞으로 오도록 설계하였다. 그러나 조금만 생각해보면 잘못 됐다는 것을 알 수 있다. 이와 같이 정렬이 돼있는 상황 가정 하에

앞에  적은 번호의 책을 가져갔다고 가정해보자 그러면 뒤에 있는 친구는 앞 친구보다는 시작번호는 클 것이다.

하지만!!   끝나는 번호 가 더 큰지에 대해서 는 알 수가 없다.  예를 들어  앞에 있는 친구가 가져갈 수 있는 책의 번호가

 3 ~9라고 해보자 뒤에 있는 친구는 3 ~ 3이다 (a 이상 b 이하 )       N이 4이고 다음에 주어야 할 책의 번호가 3이라 하면  앞에서 3번이라는 책을 주게 되면 그다음 친구는  책을 받을 수 없다... 앞에 있는 친구가 4번 책을 가져가면 다음에 있는 친구가 3번 책을 가져갈 수 있는데도 말이다.. 이러한 상황으로 인해서 우선적으로 정렬은 책의 끝 번호가 작은 번호들이 앞으로 올 수 있도록  정렬해준다. 근시적으로 작은 책들의 번호가 앞 배열로 정렬되게 된다. 이때 만약 책 끝번호가 같을 때 책의 시작 번호 중 작은 값들이 앞으로 오도록 정렬해주면 앞에 일어난 상황이 일어나지 않게 된다.

해당 번호의 책을 이미 나누어졌다는 정보를 갖기 위해 visited배열로 체크해 주었다. 

케이스 문제이므로 visited 배열을 초기화해주었다. fill을 사용할 수도 있지 만.. 2차원 배열 같은 경우 간단하게 0으로 초기화해줄 때는 memset 이 편해서.. memset을 자주 사용하고 있다.

-----------------------------------------------------------------------------------------------------------------------------------

//https://www.acmicpc.net/problem/9576
#include<iostream>
#include<cstring>
#include<algorithm>
 
using namespace std;
 
int M , N;
 
int ans ;
 
struct boo{
    int fir , sec;
};
 
boo a[1001];
 
 
int cmp(boo x , boo y)
{
    if(x.sec == y.sec )
    return x.fir < y.fir;
    
    return  x.sec < y.sec;
}
 
 
 
int visited[1001];
 
 
int main()
{
    int i,j;
    int kase;
    cin >> kase;
 
    while(kase--)
    {
        cin >> N >> M ;
        
        ans = 0 ;
        
        for(i=1; i<= M ; i++)
        cin >> a[i].fir >> a[i].sec ;
        
        //i 번째 친구 가 소유 할수 있는 책 번호 사이 값이 와야한다.
        sort(a+1 , a+1+M  , cmp );
        
        
        
        int book =1;
        
        for(i=1; i<= M ; i++)
            for(book = 1 ; book <= N; book++)
                if(a[i].fir <= book  &&  book <= a[i].sec  && !visited[book])   
                {
                    ans++;
                    visited[book] = 1;
                    break;
                }            
            
        
 
        cout << ans << "\n";
        
        memset(visited,0,sizeof(visited));
    }
 
 
    return 0;
}