BOJ 28068 I Am Knowledge

문제 링크입니다.

관찰

모든 책을 두 종류로 구분할 수 있습니다.

• 책을 읽은 후 책을 읽기 전보다 즐거움이 감소하지 않는 경우 (a ≤ b) ; 재밌는 책
• 책을 읽은 후 책을 읽기 전보다 즐거움이 감소하는 경우 (a > b) ; 재미없는 책

재밌는 책은 읽을 수 있으면 바로 읽는 게 이득입니다. 재밌는 책을 a 기준 오름차순 정렬해, 그 순서대로 읽어 줍시다. 읽을 수 없다면 0을 출력하면 됩니다.

재미없는 책 읽기

재미있는 책을 모두 읽고 즐거움을 축적한 상태를 생각해 봅시다. 이제 남은 책은 다 재미없는 책뿐입니다. 책을 볼 때마다 즐거움은 감소합니다.

재미없는 책 두 권 X, Y를 생각해 봅시다. X는 a의 즐거움을 소모해 b의 즐거움을 얻고, Y는 c의 즐거움을 소모해 d의 즐거움을 얻습니다. 이때 X를 읽고 나서 Y를 읽는 과정 중 잃는 즐거움의 최댓값은 a-b+c, Y를 읽고 나서 X를 읽는 과정 중 잃는 즐거움의 최댓값은 c-d+a입니다. 둘 중 값이 더 작은 쪽이 유리하기 때문에, 우리는 X와 Y의 순서를 b와 d 중 큰 쪽을 앞으로 배치할 수 있습니다. 이를 일반화하면 재미없는 책들을 b를 기준으로 내림차순 정렬하는 것이 최적임을 보일 수 있습니다.

따라서 총 시간 복잡도 $\mathcal{O}(N \log N)$에 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	int n; cin >> n;
	vector<pair<int, int>> v1, v2;
	for(int i = 0; i < n; i++){
		int a, b; cin >> a >> b;
		if(a <= b) v1.push_back({a, b});
		else v2.push_back({b, a});
	}
	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end());
	reverse(v2.begin(), v2.end());
	long long now = 0;
	for(auto i : v1){
		if(i.first > now) return !(cout << 0);
		now += i.second-i.first;
	}
	for(auto i : v2){
		if(i.second > now) return !(cout << 0);
		now -= i.second-i.first;
	}
	cout << 1;
}