[백준 9576 - C++] 책 나눠주기 : 그리디 알고리즘

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)

 

출력

각 테스트 케이스마다 백준이가 책을 줄 수 있는 최대 학생 수를 한 줄에 하나씩 출력한다.

 

예제 입력 1 

1

2 3

1 2

1 2

1 2

예제 출력 1 

2

 

풀이

이 문제는 그리디 알고리즘에서 매우 유명한 한 강의실에 최대의 강의 넣기와 유사하다.

이는 범위의 끝값인 b를 기준으로 오름차순 정렬이 되도록 우선순위 큐를 구현하여 해결하였다.

그렇다면 왜 b값을 기준으로 해야할까? 범위의 시작 값인 a나 범위의 크기를 기준으로 정렬하면 문제가 해결되지 않는 것일까? 라는 의문이든다.

 

우선 범위 크기를 기준으로 정렬하는 경우 문제가 되는 케이스는 아래와 같다.

1
4 4
1 2
2 3
3 4
1 3

원래 답은 4가 되어야 하지만 범위크기로 정렬하여 푸는 경우

1, 2 -> 1

2, 3 ->2

3, 4 ->3

1,3 ->못줌              이렇게 되어버린다.

 

그렇다면 시작값을 기준으로 정렬하면 어떤 문제가 생길까?

1

5 3
1 1
1 3
2 2

위의 입력의 경우

1, 1-> 1

1, 3 -> 2

2, 2 ->못줌.           이렇게 된다.

 

책의 번호가 작은 것부터 나눠주고 있기 때문에 범위의 끝값이 작은 것부터 나눠주어야하는것이다.

 

 

그렇다면 책의 번호가 큰 것부터 나눠주는 경우 범위의 시작값을 기준으로 "내림차순 정렬"해도 답이 나오지 않을까?하는 생각을 하였다. 그래서 직접해보니 되더라...ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

궁금하면 a,b 입력받고 우선순위 큐에 넣을 때 

pq.push(make_pair(a, -b));로 바꾸고

 

while문은 이렇게 바꿔서 실행해 보시길!

while(!pq.empty()){

    a = pq.top().first;

    b = -pq.top().second;

    pq.pop();

            

     for(int i=b; i>=a; i--){

           if(book[i]==false){

                book[i] = true;

                cnt++;

                break;

            }

     }

}

 

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

priority_queue<pair<int, int>> pq;
bool book[1001];


int main (void){
    int tc;
    int n, m;
    int a, b;
    int cnt= 0;
    
    scanf("%d", &tc);
    for(int i=0; i<tc; i++){
        cnt = 0;
        scanf("%d %d", &n, &m);
        for(int j=1; j<=n; j++){
            book[j] = false;
        }
        for(int j=0; j<m; j++){
            scanf("%d %d", &a, &b);
            pq.push( make_pair(-b, -a));
        }
                    
        while(!pq.empty()){
            b = -pq.top().first;
            a = -pq.top().second;
            pq.pop();
            
            for(int i=a; i<=b; i++){
                if(book[i]==false){
                    book[i] = true;
                    cnt++;
                    break;
                }
            }
        }
        printf("%d\n", cnt);
        
    }
    
}