boj, 백준) 1781. 컵라면 ( C/C++)

1. 문제 링크

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

1781번: 컵라면

 

2. 문제 개요

N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면 몇 개 줄 것인지 제시하였다. 

문제를 푸는데 단위 시간 1이 걸리며, 각 문제의 데드라인은 N이하의 자연수이다. 받을 수 있는 최대 컵라면 수를 출력하기.

 

3. 문제 힌트

데드라인이 같은 문제들을 생각해보자.. 데드라인이 같은 여러개의 문제들이 있을 어떤 문제를 선택하는 게 좋을까?

 

이제 데드라인이 다른 문제들을 생각해보자..

 

문제 (1) 데드라인 : 1  컵라면 : 5

문제 (2) 데드라인 : 2 컵라면 : 1000

문제 (3) 데드라인 : 2 컵라면 : 1000

단위시간 2 동안 어떤 문제들을 고르는 게 좋을까

 

단위 시간 1 : 문제(1)

단위 시간 2 : 문제(2)??? 

 

 

4. 문제 풀이

이 문제는 Greedy하게 접근하면 문제를 해결할 수 있다. 뭔가 DP로도 할 수 있어 보이긴 하지만..

 

우선 데드라인을 우선으로 오름차순으로 정렬하자. 그다음, 같은 데드라인에 대해서는 내림차순으로 정렬하자.

 

데드라인 순서대로 선택하기 위해서 오름차순으로 정렬했고,

같은 데드라인에 대해서 내림차순으로 정렬한 이유는 같은 데드라인인 경우, 당연히 컵라면을 더 받을 수 있는 문제를 푸는 것이 이득이기 때문이다(Greedy).

 

단, 여기서 고려해야 할 부분이 있다. (3) 번에 적었던 예처럼, 단위 시간 1일 때, 데드라인 1의 문제를 선택할 수 있다고 해서 막무가내로 선택해서는 안된다.

 

'안 고르는 것'이 최대가 될 수 있기 때문이다.

 

그래서 컵라면을 오름차순으로 하는 우선순위 큐를 하나 선언해 놓고, 선택할 때마다 이곳에 삽입한다. 데드라인을 기준으로 정렬한 것에서부터 선택을 해서 삽입해 놓은 것이기 때문에 이 우선순위 큐에 들어와 있는 애들은 빼고 다른 것을 삽입해도 데드라인에는 영향을 받지 않는다.

 

앞선 예에서,

---예---

문제 (1) 데드라인 : 1  컵라면 : 5

문제 (2) 데드라인 : 2 컵라면 : 1000

문제 (3) 데드라인 : 2 컵라면 : 1000

2개의 문제를 풀 수 있을 때 최댓값은?

------

 

우선 단위 시간 1일 때는 문제(1)을 고른다. (우선순위 큐 - 5)

두 번째, 단위 시간 2일 때는 문제(2)를 고른다. (우선순위 큐 - 5- 1000)

이제 세 번째 문제를 보는데 우선순위 큐의 Top부분이 현재 문제의 컵라면 수보다 작다면, Top에서 제거하고 지금 문제를 삽입한다. (우선순위 큐 - 1000 - 1000)

 

이런 방식으로 '선택하지 않는 경우가 최적의 경우' 일 때를 해결하면 된다.

 

 

5. 코드

문제에서는 우선순위 큐를 2개 썼지만 정렬할 때는 vector를 써도 상관없다.

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

int n;
class Comparer
{
public:
	//deadline, reward
	bool operator()(const pair<int, int> &lhs, const pair<int, int> &rhs)const
	{
		if (lhs.first < rhs.first)
		{
			return false;
		}
		else if (lhs.first == rhs.first)
		{
			return lhs.second < rhs.second;
		}
		else
		{
			return true;
		}
	}
};

priority_queue<pair<int, int>, vector<pair<int, int>>, Comparer> pq;
priority_queue<int,vector<int>,greater<int>> pqAns;

int main()
{
	scanf("%d", &n);

	for (int i = 0; i < n; ++i) {
		int deadline, reward;
		scanf("%d %d", &deadline, &reward);
		pq.push({ deadline,reward });
	}

	int round = 1;
	long long ans = 0;
	while(!pq.empty())
	{
		pair<int, int> cur = pq.top();
		pq.pop();
		if (round <= cur.first) {
			pqAns.push(cur.second);
			++round;
		}
		else
		{
			if (pqAns.top() < cur.second)
			{
				pqAns.pop();
				pqAns.push(cur.second);
			}
		}
	}

	while (!pqAns.empty())
	{
		ans += pqAns.top();
		pqAns.pop();
	}
	printf("%lld", ans);


	return 0;
}

 

6. 결과