[Beakjoon] 19700 수업 (C++)

문제 링크

BOJ 19700: 수업

문제

문제가 간단하고 명확해서 생각하는 재미가 있었다.

풀이

N이 최대 500000이라서 처음 떠오르는 방법 말고 더 효율적인 방법을 생각해보다가 반례 케이스가 많을 것 같아서 포기했다.

정직하게 팀을 구성하는 방식으로 접근했다.

키가 큰 학생부터 팀을 구성한다고 가정하자.
i번째로 큰 학생이 어떤 팀에 들어가야할지 결정할 때 i번째 학생의 최소 등수만 고려해주면 된다.

이미 구성된 팀의 구성원들은 모두 i번째 학생보다 클 것이기 때문이다. 여기서 i번째 학생의 최소 등수를 최대한 활용해주기 위해서 이분탐색을 활용한다.

만약 i번째 학생이 자신보다 큰 학생이 k명인 것까지 견딜 수 있다면 해당 학생을 배치할 때 존재하는 팀 중 팀원의 수가 k에 가까울 수록 최적의 배치이다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#define endl "\n"

using namespace std;

int N;
priority_queue<pair<int,int>> PQ;
multiset<int> Teams;

void Solve() {
    cin>>N;
    int h, k;
    for(int i=0; i<N; i++){
        cin>>h>>k;
        PQ.push({h,k});
    }

    pair<int,int> pp;
    while(!PQ.empty()){
        pp = PQ.top(); PQ.pop();
        auto iter = Teams.lower_bound(pp.second);
        if(iter == Teams.begin()){
            Teams.insert(1);
        }
        else if(*prev(iter)<pp.second){
            int count = *prev(iter);
            Teams.erase(prev(iter));
            Teams.insert(count+1);
        }
        
    }
    cout<<Teams.size();
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    Solve();

    return 0;
}