1781 컵라면

1781. 컵라면 / c++ / Gold2 / 1시간 12분 (+Hint)

문제

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

1. 문제 N개가 주어진다.
2. 각 문제는 DeadLine과, 맞췄을 때 얻는 컵라면 수가 정해져 있다.
3. 1문제당 풀이 시간 1이 소요된다고 할 때,
4. 문제를 풀었을 때 가장 많이 얻을 수 있는 컵라면의 수는?

접근 방식

그리디, 우선순위 큐

1. 문제를 우선순위 큐에 저장한다. (DeadLine이 작은 순, 그 중 CupCnt가 많은 순)
2. pq가 비어있지 않을 때까지, nowTime = 0 부터, 시작해서 pq.top().first 와 비교한다.
   1. nowTime < pq.top().first 이라면 그냥 cupPq에 추가
   2. nowTime == pq.top().first 이라면, cupPq.top()과 pq.top().second를 비교한다.
      1. cupPq.top()이 높다면 그대로 유지
      2. pq.top().second 가 높다면, cupPq.pop() 후 push (cupPq는 오름차순이라 가장 작은게 위로 옴)
3. cupPq의 모든 원소를 answer에 더한다.
4. answer 출력

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
#include <queue>
using namespace std;

struct COMP
{
    bool operator()(pair<int, int> A, pair<int, int> B)
    {
        if (A.first == B.first) A.second < B.second;

        return A.first > B.first;
    }
};

priority_queue<pair<int, int>, vector<pair<int, int>>, COMP> pq;
priority_queue<int, vector<int>, greater<int>> cupPq;

int N, deadLine, cupCnt;
int nowTime = 0, answer = 0;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> N;

    for (int i = 0; i < N; ++i)
    {
        cin >> deadLine >> cupCnt;
        pq.push({ deadLine, cupCnt });
    }

    while (!pq.empty())
    {
        if (nowTime < pq.top().first)
        {
            nowTime++;
            answer += pq.top().second;
            cupPq.push(pq.top().second);
        }
        else if (nowTime == pq.top().first)
        {
            if (cupPq.top() < pq.top().second)
            {
                answer -= cupPq.top();
                cupPq.pop();
                answer += pq.top().second;
                cupPq.push(pq.top().second);
            }
        }
        pq.pop();
    }

    cout << answer << '\n';

    return 0;
}

다시 생각해 볼 점

1. 우선순위 큐 어렵다.
2. 저번에도 제한시간 조건이 있는 그리디 문제가 나왔어서, pq를 하나 더 활용해서 그 중 제일 높은 값을 뽑아낸 적이 있었는데, 이건 그거의 응용이었다. pq를 통으로 가져가되, 만약 이미 제한시간 안의 문제를 다 채웠다면, pq 중 제일 낮은 값과 비교해서 바꿔넣는 식.
3. 이런 응용방법도 생각할 수 있어야겠다.