컵라면(그리디 알고리즘)

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

1781번: 컵라면

 

1. 각 케이스를 날짜대로 오름차순 정렬한다.

2. 현재 날짜를 0일이라고 생각한다.

3. 오름차순 정렬된 케이스를 선형탐색하여 현재 날짜보다 데드라인이 높다면 현재 날짜를 +1, 결과 우선순위 큐(오름차순)에 컵라면 갯수를 삽입해준다.

4. 결과 우선순위 큐의 Top에는 현재 날짜까지의 최적해에서 가장 적은 컵라면을 주는 케이스가 됨

5. 현재 날짜보다 데드라인이 낮거나 같은 케이스가 들어오면 결과 우선순위 큐의 Top과 비교하여 더 높은 케이스를 선택한다.

 

모든 탐색을 마친 뒤 결과 우선순위 큐의 합이 최적해가 됨.

 

#include<iostream>
#include<queue>
using namespace std;

struct compare
{
	bool operator()(pair<int, int> a, pair<int, int> b)
	{
		if (a.first == b.first) return a.second < b.second;
		else return a.first > b.first;
	}
};

struct second_compare
{
	bool operator()(pair<int, int> a, pair<int, int> b)
	{
		return a.second > b.second;
	}
};

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;

	int cmd;
	cin >> cmd;
	while (cmd--)
	{
		int d, c;
		cin >> d >> c;

		pq.push(pair<int, int>(d, c));
	}
	
	priority_queue<int, vector<int>, greater<int>> retpq;
	int curday = 0;
	while (!pq.empty())
	{
		int day = pq.top().first;
		int ramen = pq.top().second;
		pq.pop();

		if (curday < day)
		{
			curday++;
			retpq.push(ramen);
		}
		else
		{
			if (retpq.top() < ramen)
			{
				retpq.pop();
				retpq.push(ramen);
			}
		}
	}

	int ret = 0;
	while (!retpq.empty())
	{
		ret += retpq.top();
		retpq.pop();
	}

	cout << ret << '\n';
}