[백준] 9576 책나눠주기 (Greedy Algorithm)

How to solve

1. 입력 받기

2. student를 b에 대해서 sort b->a 기준으로 오름차순 sort

3. M명의 학생에 대해서 책 a~b까지 보고 한개씩 나눠줌

4. 책에 대해서 check vector를 만들어 나누어준 책 표시

5. 나누어준 책 count

 

---

Problem

책 나눠주기 성공분류

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

256 MB

5394

1495

1020

26.977%

문제

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

 

---

Solution

 

#include <bits/stdc++.h>
#include <iostream>

#define int long long 

using namespace std;
int T; //test case
int N, M;//M student, N book

vector<pair<int, int> > student;
vector<bool> book(1002, false);

void input_data(){
    
    cin >> N >> M;
    for(int i=0; i<M; i++){
        int a, b;
        cin >> a >> b;
        student.push_back({a, b});
    }
}
bool comp(pair<int, int> a, pair<int, int> b){
    if(a.second < b.second){
        return true;
    }else{
        if(a.second == b.second){
            if(a.first < b.first){
                return true;
            }
        }
        return false;
    }
}
void solve(){
    //second 기준 오름차순 정렬
    sort(student.begin(), student.end(), comp);
    //M 학생 나눠주기
    for(int i=0; i<M; i++){
        for(int j=student[i].first; j<=student[i].second; j++){
            if(!book[j]){
                book[j] = true;
                break;
            }
        }
    }
}

int count_book(){
    int cnt = 0;

    for(int i=0; i<=N; i++){
        if(book[i] == true){
            cnt++;
        }
    }

    return cnt;
}

void init(){
    student.clear();
    book.clear();
    book.assign(1002, false);
}

void print_data(){
    for(int i=0; i<=N; i++){
        cout << book[i] << ' ';
    }
}
signed main(){
    cin >> T;
    while(T--){
        init();
        input_data();
        solve();
        int res = count_book();
        cout << res << endl;
        // print_data();
    }
    return 0;
}