[백준] 1781번 컵라면

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;

const int MAX = 200001;
int N;
vector<int> problems[MAX];

int optimize(){
    int ret = 0;
    priority_queue<int, vector<int>, less<int>> pq;
    for(int day=N; day>=1; day--){
        for(auto p:problems[day]) pq.push(p);
        if(!pq.empty()){
            ret+=pq.top(); pq.pop();
        }
    }
    return ret;
}

int main(){
    fastio;
    cin>>N;
    for(int i=0; i<N; i++){
        int ddln, rm;
        cin>>ddln>>rm;
        problems[ddln].push_back(rm);
    }
    cout<<optimize();
    return 0;
}

<참고>

https://please-amend.tistory.com/184

<풀이>

1. priority_queue<int, vector<int>, less<int>> pq; 

push()로 값을 넣으면 자동으로 우선순위에 따라 정렬해서 top()을 호출하면 가장 우선순위 높은 값이 나옴

less<int>: 정렬 기준 → 큰 값이 우선순위 높음(Max Heap) 즉 내림차순 정렬 구조이다.

Max heap: 

      10
     /  \
    1    5 구조로 되어 있다.

 

2. 시간 역순으로 매일 가능한 문제 중 가장 컵라면을 많이 받을 수 있는 문제를 풀도록 한다.

<문제>

컵라면 수: 2^31보다 작은 자연수

N: 숙제의 개수

데드라인, 컵라면 수를 입력받음 -> 받을 수 있는 최대 컵라면 수는?

데드라인: 3이라면 1,2,3 중 아무때나 풀 수 있는 것