문제

2109번 문제

코드

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

int n;
vector<pair<int, int>> v;

bool compare(pair<int, int>& p1, pair<int, int>& p2)
{
	return p1.second < p2.second;
}

int main()
{
	cin >> n;

	priority_queue<int, vector<int>, greater<int>> pq;

	while (n--)
	{
		pair<int, int> p;
		cin >> p.first >> p.second;
		v.push_back(p);
	}

	sort(v.begin(), v.end(), compare);

	for (auto p : v)
	{
		pq.push(p.first);

		if (pq.size() > p.second)
		{
			pq.pop();
		}
	}

	int sum = 0;
	while (!pq.empty())
	{
		sum += pq.top();
		pq.pop();
	}

	cout << sum;
}

풀이

전형적인 그리디 문제
우선순위 큐를 사용할 줄 알고 이런 비슷한 문제를 풀다 보면 어떻게 풀어야 하는지 감이 온다(나도 슬슬 잡는 중)

1. pair<int, int> 타입을 이용해 사용자의 입력을 받는다
2. d일 안에 와서 강의를 해야 하는 데 이 값을 기준으로 오름차순 정렬한다
3. 벡터를 순회하며 우선순위 큐에 p값을 push하고 특정 조건에서 pop한다
4. 그렇게 완성된 우선순위 큐를 순회하며 합을 구한다

사용자의 입력 p와 d를 받아 정렬 시킬 때 원래 sort 함수를 사용하면 first 값을 기준으로 오름차순하는데 우리는 second로 정렬시켜야 해서 커스텀 정렬 함수를 선언했다

우선순위 큐에 first값을 넣을 때 마다 first 값이 작은 순으로 pop이 된다. 그래서 우선 first 값을 넣으면 알아서 작은 값이 먼저 pop되게 정렬된다

그래서 우선순위 큐에 push를 하다가 현재 우선순위 큐의 size가 현재 제안(pair)의 second보다 크다는 것은 그 날 안까지 그 대학에 가서 강연을 못한다는 말이 된다

예를 들어 먼저 (20, 1)을 우선순위 큐에 넣으면 문제 없이 push되고 다음 (2, 1)을 push하면 1일인데 강연을 2개나 한다는 뜻이 되기 때문에 작은 값을 제안한 대학을 포기한다는 의미임

이는 다른 해설을 보면 이해가 잘 될 것이라고 생각함!

이렇게 그리디 문제를 접근하는게 공략같다