티스토리 뷰
1. 문제 링크
https://www.acmicpc.net/problem/1781
1781번: 컵라면
상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라
www.acmicpc.net
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. 결과
'알고리즘 > Greedy' 카테고리의 다른 글
boj, 백준) 2212. 센서 (C / C++) (0) | 2021.08.14 |
---|---|
boj, 백준) 1911. 흙길 보수하기(C/C++) (0) | 2021.08.12 |
boj, 백준) 1135. 뉴스전하기 (C/C++) (0) | 2021.05.27 |
boj, 백준) 3109 빵집 ( C++) (0) | 2020.02.28 |
boj, 백준) 2812 크게만들기( C, C++ ) (2) | 2020.02.28 |