[C++] 백준 1781번: 컵라면

문제

난이도 : 골드 2
백준 1781번 : 컵라면

코드

#include <bits/stdc++.h>

using namespace std;

int N;
vector<pair<int, int>> v;
priority_queue<int, vector<int>, greater<int>> pq;

int main()
{
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        int a, b;
        cin >> a >> b;
        v.push_back({ a, b });
    }

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

    for (int i = 0; i < v.size(); i++)
    {
        if (pq.size() < v[i].first)
        {
            pq.push(v[i].second);
        }
        else if (pq.size() == v[i].first && pq.top() < v[i].second)
        {
            pq.pop();
            pq.push(v[i].second);
        }
    }

    int ret = 0;

    while (pq.size())
    {
        ret += pq.top(); pq.pop();
    }

    cout << ret;

    return 0;
}

풀이

그리디 문제
데이터를 입력 받을 pair<int, int>형 벡터와 오름차순으로 정렬이 되는 priority_queue를 이용한다
벡터에 데이터를 입력 받고 sort 시켜주면 데드라인 순으로 오름차순 정렬 후 컵라면 수 순으로 오름차순 정렬된다
우선순위 큐 pq의 size보다 데드 라인이 크면 학습이 불가한 것으로 이해했다. 1차적으로 데드라인이 작은 것부터 우선순위 큐에 넣기 때문에 우선순위 큐의 size를 day로 이해해도 된다?
만약 우선순위 큐의 size와 현재 문제의 데드라인이 같고 현재 문제가 우선순위 큐의 top보다 컵라면 수가 더 많으면 우선순위 큐를 pop하고 현재 문제를 push한다
예를 들어 {1, 6}인 문제가 큐에 들어가고 {1, 7}인 문제를 볼 때 데드라인 안에 풀 수 있는 문제면 컵라면을 더 많이 주는 문제를 풀어야 하기에 {1, 6}을 빼낸다. 여기서 우선순위 큐에는 오름차순으로 정렬이 되기에 우선순위 큐의 top에는 제일 작은 컵라면 수가 들어있음. 그렇게 우선순위 큐가 완성되면 하나씩 빼서 결과를 출력하면 된다.

결과