백준 9576번 책 나눠주기 c++ 풀이

문제

백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 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

 

그리디 문제였다.

이분매칭으로 푸는 방법도 있었지만 그리디로 풀었다.

이 문제의 핵심은 정렬을 어떻게 하느냐에 따라서 정답이 갈리게 된다.

 

정렬을 숫자가 시작되는 부분을 기준으로 오름차순 정렬을 하게 되면

숫자를 제대로 카운트 할 수 없게 된다.

따라서 숫자가 끝나는 부분을 기준으로 오름차순 정렬을 하게 되면

정답을 제대로 도출할 수 있게 된다.

 

예를 들어서 

 

1

5 3
1 1
1 3
2 2

 

위와 같은 입력이 주어졌을 때

첫번째 숫자를 기준으로 오름차순 정렬을 하게 되면

 

1 1

1 3

2 2

가 된다.

 

두번째 숫자를 기준으로 오름차순 정렬을 하게 되면

 

1 1

2 2

1 3

이 된다.

 

먼저 첫번째 정렬과 같은 상태로 정답을 구하게 된다면

순서대로

첫번째 입력일 때 ans ++ , visited[1] = true

두번째 입력일 때 ans ++ visited[2] = true

세번째 입력일 때 visited[2] = true 이기 때문에 ans++ 가 되지 않는다.

 

두번째 정렬과 같은 상태로 정답을 구하게 된다면

순서대로

첫번째 입력일 때 ans ++ , visited[1] = true

두번째 입력일 때 ans ++ , visited[2] = true

세번째 입력일 때 ans ++ , visited[3] = true

가 되어서 제대로 정답을 구할 수 있게 된다.

 

- c++

#include <bits/stdc++.h>
using namespace std;

bool comp(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(void){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T;
    cin >> T;

    while(T--){

        int n,m;
        int ans=0;
        int visited[1001]={0,};
        cin >> n >> m;

        vector<pair<int,int>>book;

        for(int i = 0 ; i < m; i++){
            int a,b;
            cin >> a >> b;
            book.push_back({a,b});
        }

        sort(book.begin(),book.end(),comp);


        for(int i = 0 ; i < book.size(); i++){
            for(int j = book[i].first; j<= book[i].second; j++){
//                cout << j << "\n";

                if(visited[j]==1){
                    continue;
                }

                if(visited[j]==0){
                    visited[j]=1;
                    ans++;
                    break;
                }
            }
        }

        cout << ans << "\n";
    }


    return 0;
}