BOJ 1781 - 컵라면

문제

상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라인을 정하였다.

위와 같은 상황에서 동호가 2, 6, 3, 1, 7, 5, 4 순으로 숙제를 한다면 2, 6, 3, 7번 문제를 시간 내에 풀어 총 15개의 컵라면을 받을 수 있다.

문제는 동호가 받을 수 있는 최대 컵라면 수를 구하는 것이다. 위의 예에서는 15가 최대이다.

문제를 푸는데는 단위 시간 1이 걸리며, 각 문제의 데드라인은 N이하의 자연수이다. 또, 각 문제를 풀 때 받을 수 있는 컵라면 수와 최대로 받을 수 있는 컵라면 수는 모두 231보다 작거나 같은 자연수이다.

입력

첫 줄에 숙제의 개수 N (1 ≤ N ≤ 200,000)이 들어온다. 다음 줄부터 N+1번째 줄까지 i+1번째 줄에 i번째 문제에 대한 데드라인과 풀면 받을 수 있는 컵라면 수가 공백으로 구분되어 입력된다.

출력

첫 줄에 동호가 받을 수 있는 최대 컵라면 수를 출력한다.

접근

옛날에 풀었던 비행기 도킹 문제와 비슷한 문제라고 생각했다.
그래서, 각 시간마다 parent를 두고 Union-Find로 풀고자 했다.

여기서 고려해야될 점은 데드라인의 범위가 적혀있지 않다는 점이다.
생각해보면 N보다 데드라인이 크다면, 무조건 받을 수 있는 값이다.
이 경우만 예외처리를 해주고,
우선순위큐를 사용해서 컵라면을 많이 주는 문제부터 해결하면 된다.

풀이

처음 입력을 받을 때, N보다 데드라인이 큰 경우는 ans에 무조건 더해줬다.
그렇지 않은 경우는 컵라면 수의 내림차순으로 들어갈 pq에 넣어줬다.

이후로는 pq에서 하나씩 pop하면서, 데드라인에 find를 취해주면 된다.
이 값이 0이 나오는 경우는 문제를 풀 수 없는 경우를 의미한다.
그렇지 않은 경우는 부모값과 부모값 - 1을 update해서 사용했음을 알리고, ans에 더해준다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

int N, a, b, ans = 0, parent[200001];

int find(int x)
{
	if (x == parent[x]) return x;
	return parent[x] = find(parent[x]);
}

void update(int x, int y)
{
	if (x > y) swap(x, y);
	x = find(x);
	y = find(y);
	parent[y] = x;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	priority_queue<pair<int, int>> pq;
	CIN(N);
	FUP(i, 1, N)
	{
		parent[i] = i;
		CIN2(a, b);
		if (a >= N) ans += b;
		else pq.push({ b, a });
	}
	while (!pq.empty())
	{
		int cup = pq.top().first;
		int deadline = pq.top().second;
		pq.pop();
		int idx = find(deadline);
		if (idx == 0) continue;
		ans += cup;
		update(idx, idx - 1);
	}
	COUT(ans);

	return 0;
}