[백준 c++] 1781 컵라면

문제 설명

https://www.acmicpc.net/problem/1781
상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라인을 정하였다.

문제 번호 1 2 3 4 5 6 7
데드라인 1 1 3 3 2 2 6
컵라면 수 6 7 2 1 4 5 1
위와 같은 상황에서 동호가 2, 6, 3, 1, 7, 5, 4 순으로 숙제를 한다면 2, 6, 3, 7번 문제를 시간 내에 풀어 총 15개의 컵라면을 받을 수 있다.

문제는 동호가 받을 수 있는 최대 컵라면 수를 구하는 것이다. 위의 예에서는 15가 최대이다.

문제를 푸는데는 단위 시간 1이 걸리며, 각 문제의 데드라인은 N이하의 자연수이다. 또, 각 문제를 풀 때 받을 수 있는 컵라면 수와 최대로 받을 수 있는 컵라면 수는 모두 231보다 작거나 같은 자연수이다.

입력
첫 줄에 숙제의 개수 N (1 ≤ N ≤ 200,000)이 들어온다. 다음 줄부터 N+1번째 줄까지 i+1번째 줄에 i번째 문제에 대한 데드라인과 풀면 받을 수 있는 컵라면 수가 공백으로 구분되어 입력된다.

출력
첫 줄에 동호가 받을 수 있는 최대 컵라면 수를 출력한다.

풀이

2109 순회강연과 비슷한 문제였다. 그래서 순회강연 문제처럼 풀었더니 시간초과가 났다. 컵라면 수를 기준 내림차순 정렬한 우선순위 큐를 for을 돌며 배열에 채우는 식으로 풀려고 했는데 이 문제는 N이 최대 20만이라서 만약 모든 데드라인이 20만인 경우 2초 안에 연산이 불가능하다.

오름차순 정렬 pair vector
오름차순 정렬(컵라면 개수) priority_queue를 이용한 풀이

1. 입력을 오름차순으로 정렬해서 pair vector에 저장
2. priority_queue에 컵라면 개수 push, result+=컵라면 개수
3. 만약 pq.size가 데드라인보다 크다면 pq.pop, result-=컵라면 개수

데드라인 1 1 2 2
컵라면수 2 7 4 5

(1,2) -> pq[2] result= 2
(1,7) -> pq[2, 7] result= 2+7 //pq.size()>데드라인(1)

=> pq[7] result= 7

(2,4) -> pq[4,7] result= 7+4
(2,5) -> pq[4,5,7] result= 7+4+5 //pq.size()>데드라인(2)

=> pq[5,7] result=7+5

정답: 12

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int n, p, d, res;
vector<pair<int, int>> v;
priority_queue<int, vector<int>, greater<int>> q;
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> d >> p;
        v.push_back({d, p});
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < v.size(); i++)
    {
        res += v[i].second;
        q.push(v[i].second);
        if (q.size() > v[i].first)
        {
            res -= q.top();
            q.pop();
        }
    }
    cout << res << "\n";
}