취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 28068번 문제인 I Am Knowledge이다.
문제는 아래 링크를 확인하자.

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

각 책을 (a,b)와 같이 나타낸다면, 해당 책은 마법사의 즐거움이 a 이상일 때 읽어 즐거움을 b-a만큼 증가시켜줄 수 있다. (단, b-a가 음수이면 a-b만큼 감소한다.) 모든 책을 읽는 방법이 존재한다면 순서를 적절히 조절해 '책을 읽기 전과 비교했을 때 읽은 뒤 즐거움이 증가하는 책'들을 모두 읽고 그렇지 않은 책들을 마저 읽어 모든 책을 읽을 수도 있음을 관찰하자.

읽은 뒤 즐거움이 증가하는 책들을 조건을 만족하도록 전부 읽는 것이 가능한지는 그러한 책들을 a값을 기준으로 오름차순 정렬했을 때 이 책들을 그 순서대로 읽어나갈 수 있는지를 확인하는 것으로 해낼 수 있다.

읽은 뒤 즐거움이 감소하는 책들을 차례대로 읽을 수 있는지를 생각해보자. 만약 그러한 방법이 존재한다면 모든 책을 다 읽었을 때의 최종 즐거움 값은 (모든 b의 값의 합) - (모든 a의 값의 합)이 될 것이다. 이 즐거움 값에서 시작해 즐거움이 감소하는 책을 읽어나가던 과정을 거꾸로 실행해나가는 것은 '현재 즐거움 값이 b 이상일 때 읽어 즐거움을 a-b(>0)만큼 증가시키는' 책을 읽어나가는 것으로 생각할 수 있다. 이것이 앞선 문단의 경우와 동일함을 관찰하면 이 또한 같은 방법으로 해결할 수 있음을 알 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

int N;
vector<pair<int, int>> vec1, vec2;
ll val1, val2;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	while (N--) {
		int a, b; cin >> a >> b;
		val1 += (b - a);
		if (a > b) vec1.emplace_back(make_pair(b, a - b));
		else vec2.emplace_back(make_pair(a, b - a));
	}

	sort(vec1.begin(), vec1.end());
	sort(vec2.begin(), vec2.end());

	for (auto& p : vec1) {
		if (val1 < p.first) {
			cout << 0;
			return 0;
		}
		val1 += p.second;
	}

	for (auto& p : vec2) {
		if (val2 < p.first) {
			cout << 0;
			return 0;
		}
		val2 += p.second;
	}

	cout << 1;
}