Boj 1781) 컵라면

문제

백준 1781

설명

데드라인이 있어서 가장 보상이 좋은 문제만 고를 수가 없다. 하지만 조금만 생각을 바꾸면 간단한 그리디 정책을 떠올릴 수 있다. 바로 모든 시간대에서 최대한 꿀문제만 고르는 것이다. 증명은 간단하므로 생략한다.

이를 좀더 구체화한 전략은 다음과 같다. i 시간 이하의 문제를 그룹에 넣고, 보상에 대해 정렬했을 때 인덱스가 i 보다 큰 경우를 모두 배제한다. 시간을 i+1 로 올리고 이를 반복한다.

• 이때 우선순위 큐를 사용하면 정렬된 상태를 유지하고 크기를 일정하게 유지하는 것을 간단하게 구현할 수 있다.
• 또한 굳이 시간을 1 단위로 세지않고 데드라인 단위로 해도 된다. 데드라인이 짧은 시간부터 큐에 넣어 가장 최근에 넣은 데드라인과 큐의 크기를 비교하면 된다.

시간 복잡도

O(\(\mathrm{N}\log{\mathrm{N}}\))

코드

struct Item
{
	int dead, cup;
	bool operator()(const Item& a, const Item& b) { return a.cup > b.cup; }
} items[200001];


int main()
{
	int n; cin >> n;
	for (int i = 0; i < n; i++)
		cin >> items[i].cup >> items[i].dead;

	priority_queue<Item, std::vector<Item>, Item> pq;
	sort(items, items + n, [](Item& a, Item& b) { return a.dead < b.dead; });

	for (int i = 0, t = 0; i < n; i++)
	{
		pq.push(items[i]);
		if (items[i].dead < pq.size())
			pq.pop();
	}

	long long ans = 0;
	while (pq.size())
	{
		ans += pq.top().cup;
		pq.pop();
	}

	cout << ans;
}