BOJ 19700 : 수업

 

#BOJ 19700 : 수업

19700번: 수업

#풀이

multiset을 이용하여 multiset의 메소드인 lower_bound 를 사용하여 해결할 수 있다.

 

키와 k를 받지만 사실 키는 신경쓰지 않아도 된다. 그 이유는 키가 큰 순서대로 정렬하여 각 팀에 있는 인원 수 가 k보다 작은 곳에 들어가야하므로 k만 생각하고 풀면 된다.

 

multiset을 사용하여 팀의 각 몇명있는지 확인하여 k보다 작은 팀중에서 가장 많은 수의 팀원이 있는 팀을 들어가야한다.

 

multiset을 사용하는 이유는 이진트리로 구현되어 있고 set이랑 다르게 중복이 가능하다.

각 팀의 팀원의 수가 같을 수 도 있으므로 팀원 수가 중복되어야 한다.

 

#코드 

 

#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
int n;
int ans = 0;
vector<pair<int,int>> v;
multiset<int> team;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		int h; int k;
		cin >> h >> k;
		v.push_back({ h,k });
	}
	sort(v.begin(), v.end());
	
	for (int i = n-1; i >= 0; i--) {
		int cur = v[i].second;
		auto loc = team.lower_bound(cur);
		if (loc == team.begin()) team.insert(1);
		else {
			auto rloc = prev(loc);
			if (*rloc < cur)
			{
				int new_re = *rloc + 1;
				team.erase(rloc);
				team.insert(new_re);
			}
			else {
				team.insert(1);
			}
		}
	}
	
	cout << team.size() << '\n';
	return 0;
}