BOJ 28068 - I Am Knowledge

 

문제가 원하는 것은 마법사가 책을 자지 않고 다 읽을 수 있는지 판별해 주는 것이다.

마법사는 책을 읽을 때 즐거움 ai 만큼 소모하고 다 읽으면 bi 만큼 즐거움을 얻는다.

 

관찰 1.

우선 ai ≤ bi인 책을 읽으면 읽기 전보다 즐거움이 감소하지 않는다.

따라서 이런 책만 읽을 때에는 ak가 작은 순서대로 읽으면 된다.

 

관찰 2.

다음으로 ai > bi인 경우이다.

이 경우 책을 읽을 때마다 즐거움이 감소한다.

따라서 책을 거꾸로 읽는 방법을 생각해 보면 되는데 이 경우에는 관찰 1번과 같은 방법을 사용하면 된다.

그렇기에 bi가 큰 순서대로 읽으면 된다.

 

이제 즐거움이 감소하지 않는, 이득이 되는 책을 전부 읽은 후 이득이 되지 않는 책을 읽으며

즐거움이 0 밑으로 떨어지는지 확인하면 정답을 구할 수 있다.

 

처음에는 단순히 우선순위 큐에 넣고 ai 값이 작은 순으로 빼서 확인하는 식으로 하면 되는 줄 알았지만 아니었다..

생각보다 어려웠던 문제였다.

---

소스코드

#include <bits/stdc++.h>
#define endl "\n"
#define upgrade ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
bool cmp(pair<ll, ll>a, pair<ll, ll>b) {
	if (a.first == b.first)return a.second < b.second;
	return a.first < b.first;
}
bool cmp2(pair<ll, ll>a, pair<ll, ll>b) {
	return a.second > b.second;
}
int main() {
	upgrade;
	int n;
	cin >> n;
	vector<pair<ll, ll>>p;
	vector<pair<ll, ll>>m;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		if (a <= b)p.push_back({ a,b });
		else m.push_back({ a,b });
	}
	sort(all(p), cmp);
	sort(all(m), cmp2);
	ll happy = 0;
	for (int i = 0; i < p.size(); i++) {
        happy -= p[i].first;
		if (happy < 0) {
			cout << 0;
			return 0;
		}
		happy += p[i].second;
	}
	for (int i = 0; i < m.size(); i++) {
        happy -= m[i].first;
		if (happy < 0) {
			cout << 0;
			return 0;
		}
		happy += m[i].second;
	}
	cout << 1;
	return 0;
}