문제 출처

1. 문제설명

  • 어떤 문제에 데드라인과 얻을 수 있는 컵라면 수가 있다.
  • 문제를 해결하면 컵라면을 받을 수 있다.
  • 이 때 받을 수 있는 최대 컵라면 수를 구하라


2. 알고리즘 설계

  • 첫 접근
    • 데드라인에 따라 정렬하고, 데드라인이 같다면 컵라면 수로 정렬한다.
    • pq의 top은 데드라인이 가장 빠르고, 그 중 컵라면 수가 많은 게 나올 것이다.
    • top의 데드라인이 현재 비교용 데드라인과 다르다면 더하고 아니라면 건너 뛴다.
  • 첫 접근 문제점
    • 데드라인이 [1, 2], [2, 5], [2, 10]가 있다고 해보자
    • 내 기존 코드는 [1, 2]와 [2, 10]을 골라 답이 12가 나왔을 것이다.
    • 그러나 실제 정답은 2->10->5로 17이 된다.
    • 마감 2를 끝내면 또 다른 마감 2를 해결할 수 있는 것이다.
  • 해결한 접근법
    • 데드라인의 최대 N은 200,000이다.
    • 2차원 배열([데드라인][컵라면 개수])을 사용해 미리 저장해둔다.
    • 앞서 마감 N을 끝내면 또다른 마감 N을 해결할 수 있다고 언급했다.
    • 기존과 달리 뒤에서부터 pq에 넣어 큰 원소대로 집어넣었다.


3. 전체 코드

#include <bits/stdc++.h>
using namespace std;
using ui = unsigned int;

int n, d, c, mx;
ui ans;
vector<ui> v[200'005];
priority_queue<ui> pq;


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

    cin >> n;
    while(n--) {
        cin >> d >> c;
        v[d].push_back(c);  // 데드라인마다 벡터를 생성해 컵라면 개수를 집어넣는다.
        mx = max(mx, d);  // 밑에 for문에서 최대 N(200,000)부터 돌리지 않기 위해서
    }

    for(int i=mx; i !=0; i--) {  // 마지막 데드라인부터 탐색해서
        for(ui a : v[i])    // 원소가 있다면 pq에 삽입
            pq.push(a);
        
        if(pq.empty()) continue;
        ans += pq.top();  // pq의 top이 현재 내가 취할 수 있는 최대값이 된다.
        pq.pop();
    }

    cout << ans;

    return 0;
}