백준 g1 19700 수업 c++

https://www.acmicpc.net/problem/19700

19700번: 수업

 

문제

N명의 학생의 키 H, 최소 등수 Ki가 주어진다.

학생들은 팀원 중에 자신보다 키가 큰 사람이 Ki명 이상이면 수업을 거부한다고 한다.

최소 몇 개의 팀을 짤 수 있는가?

 

풀이

아이디어를 생각해내기도 정말 어려웠던 문제이다. 결국 답지를 찾아봤음

 

핵심은 학생들의 키와 등수에 연연하지 말고 팀원 수에 신경 쓰는 것

키를 내림차순으로 정렬한 후에 팀에 차곡차곡 쌓아나가면 그게 그 사람의 등수가 된다.

 

예를 들어 팀원이 3명인 팀에 들어가는 4번째 팀원은 그 팀의 4등이 된다.

결국 중요한 건 꼴찌의 키도 아니고 팀원 수가 중요한 것 .. 

 

ex. 최소 등수가 4면 인원수가 4 미만인 팀에 들어가면 된다.

어차피 키 내림차순으로 팀을 배정하기 때문에 내 등수가 밀려날 일은 없다. 

 

수도 코드

키 배열 정렬

for: 큰 키부터
	it = team.lower_bound(최소 등수 == 원하는 팀원 수-1)
    if 만족하는 팀이 없으면
    	team.insert(1) // 새로 제작
    else
    	해당 팀 인원 수++

 

여기서 또 문제가 있는데, 내가 원하는 건 인원 수가 k 이하인 팀인데, STL set에는 lower_bound나 upper_bound로 인원 수 이상이나 초과 밖에 못 구한다. 딱 반대로 동작하는 함수가 있으면 좋을텐데 ...

-> 인원수에 -를 붙여서 배열을 거꾸로 놔주면 해결할 수 있다.

 

ex

-4 -4 -3 -2 -2

내 최소 등수가 3등이면, -3의 upper_bound인 -2부터 들어갈 수 있는 팀이다.

 

전체 코드

/*boj g1 19700 수업*/
#include <algorithm>
#include <iostream>
#include <set>
#define MAXN 500005
using namespace std;

int N;
pair<int, int> stud[MAXN];
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> stud[i].first >> stud[i].second;
    }

    sort(stud, stud + N, greater<>());

    multiset<int> team;

    for (int i = 0; i < N; i++) {
        int h = stud[i].first;
        int r = stud[i].second;

        auto it = team.upper_bound(-r);

        if (it == team.end()) {
            team.insert(-1);
        } else { // 만족할 수 있는 해당 팀에 학생을 넣는다
            int num = *(it);
            team.erase(it);
            team.insert(num - 1);
        }
    }

    cout << team.size() << "\n";
}

 

---

매우 도움이 되었던 참고

https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x16/solutions/19700.cpp

https://codingnotes.tistory.com/192