[BOJ] 백준 19700. 수업 (Gold I)

아이디어는 크게 어렵지 않으나, 시간이 상당히 빡빡한 문제이다.

문제는 아래와 같다.

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

19700번: 수업

---

의식의 흐름 및 해설

팀에서 자신보다 키가 큰 학생들이 Ki명 이상이면 수업을 째버리겠다는 굉장히 이상한 수강생들만 존재하는 수업이다. 나중에 사회생활은 어떻게 하려는거지 ㄷㄷ

이는 자신보다 키가 큰 학생이 Ki-1명 이하여야 한다는 소리이며, 키큰 순서대로 등수를 매길 때, Ki 등이어야 한다는 소리와 같다.

 

즉, Ki가 1일 경우는 무조건 새로운 팀을 만들어서 진행한다는 소리인데,

이를 통해 키가 큰 순서대로 먼저 배치해주면 i번째 인원을 배치할 때, 현재 배치된 i-1명은 모두 자신보다 키가 크기 때문에 팀원이 Ki-1명 이하인 팀에 들어가야 함이 자명하다. 

이를 이용해 그리디적으로 해결하면 되는데... 문제는 팀원 사이즈를 기록해둔 배열을 매번 정렬하는 풀이로 접근한다면 O(N^2lgN)이므로 시간초과를 겪게 된다는 점이다.

    cin >> N;
	for (int i = 0; i < N; i++) {
		int h, n;
		cin >> h >> n;
		pq.push({ h, n });
	}
	while (!pq.empty()) {
		int n = pq.top().second;
		pq.pop();
		sort(all(v));
		int idx = lower_bound(all(v), n) - v.begin() - 1;
		if(idx>=0 && idx<v.size())
			v[idx]++;
		else {
			v.push_back(1);
			ans++;
		}
	}

51% 쯤에서 시간초과를 겪은 코드

 

두 가지 방법이 있는데, 하나는 multiset을 이용하여 팀원 사이즈를 저장해두고 (set 성격 상 자동으로 정렬이 됨)

이를 이용해 이분탐색을 돌려서 확인하면 된다. set, map에서도 lower_bound, upper_bound가 되는 건 또 첨 알았다.

 

다른 방법은, upper_bound을 내림차순에서 이용하는 방법인데, 이 방법이 신기해서 포스팅하려 한다.

사실 조금만 더 생각해보면, 팀원 사이즈는 처음 정렬해주면, 그 이후론 항상 내림차순으로 정렬된다는 것을 알 수 있다.

팀이 새로 생성될 때는 팀원이 1명인 새로운 팀을 만드는 것이므로 가장 적은 사이즈임이 분명하고,

팀원이 추가될 때는, 값이 n 미만인 것 중 최대인 값을 1 증가시키므로, 값이 같아지는 경우는 존재할 수 있어도, 역전되는 경우는 존재하지 않음을 알 수 있다. 만약 헷갈리면 multiset 풀이로 하면 된다 ㅎㅎ 나도 첨에 몰라서 걍 그렇게 했었다.

int idx = upper_bound(all(v), n, greater<int>()) - v.begin();

위와 같이 greater<int>()를 붙여주면 upper_bound는 내림차순 정렬에서 값이 n 미만인 것 중 최대인 인덱스를 리턴해준다. 참고로 lower_bound로 하면 값이 n 이하인 것의 인덱스를 리턴해준다.  

---

코드

multiset을 이용한 풀이 (400ms)

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
const int MAX = 500011;
const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
int N, ans;
priority_queue<pi> pq;
multiset<int> S;
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N;
	for (int i = 0; i < N; i++) {
		int h, n;
		cin >> h >> n;
		pq.push({ h, n });
	}
	while (!pq.empty()) {
		int n = pq.top().second;
		pq.pop();
		int s = 0, e = n - 1, res = -1;
		while (s <= e) {
			int mid = (s + e) / 2;
			auto it = S.upper_bound(mid);
			if (it != S.end() && *it < n) {
				res = mid;
				s = mid + 1;
			}
			else
				e = mid - 1;
		}
		if (res != -1) {
			S.erase(S.find(res + 1));
			S.insert(res + 2);
		}
		else {
			S.insert(1);
			ans++;
		}
	}
	cout << ans << "\n";
}

upper_bound를 이용한 풀이 (176ms)

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
const int MAX = 500011;
const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
int N, ans;
priority_queue<pi> pq;
vector<int> v;
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N;
	for (int i = 0; i < N; i++) {
		int h, n;
		cin >> h >> n;
		pq.push({ h, n });
	}
	while (!pq.empty()) {
		int n = pq.top().second;
		pq.pop();
		int idx = upper_bound(all(v), n, greater<int>()) - v.begin();
		if (idx == v.size())
			v.push_back(1);
		else
			v[idx]++;
	}
	cout << v.size() << "\n";
}

---

쉬운 줄 알았는데 생각보다 까다로운 문제...

재밌었다.

 

multiset이 꼭 필요한 경우는 이 문제를 통해 첨봤는데, 좋은 경험이 된 듯하다. (물론 upper_bound 성질과, 문제의 조건을 제대로 파악했다면 필요없음)

D번도 재밌어보이던데 나중에 시간나면 풀어봐야지