BOJ 1781 : 컵라면

풀이 요약

우선순위 큐

풀이 상세

1. 데드라인과 컵라면 수를 받는 벡터를 생성하여 정렬한다. 정렬 기준은 기본 오름차순이다.

2. 오름차순의 우선순위큐를 받아 일단 컵라면 수들을 담는다. 단 현재 데드라인 보다 우선순위큐의 사이즈가 큰 경우가 나타난다면 현재까지의 숙제가운데 어떠한 것을 포기해야한다는 뜻이며, 이때 가장 적게 받는 컵라면 수를 빼도록 하자.

3. 남아있는 우선순위 큐의 총 수가 최대로 받을 수 있는 컵라면의 수이다.

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
priority_queue<int, vector<int>, greater<int>> pq;
int N, ret;
vector<pair<int, int>> v;

void input() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    int a, b;
    for (int i = 0; i < N; i++) {
        cin >> a >> b;
        v.push_back({a, b});
    }
    sort(v.begin(), v.end());
}

void solve() {
    for (int i = 0; i < v.size(); i++) {
        pq.push(v[i].second);
        if (pq.size() > v[i].first) pq.pop();
    }
    while (!pq.empty()) {
        ret += pq.top();
        pq.pop();
    }
}

void output() {
    cout << ret;
}

int main() {
    input();
    solve();
    output();
}