[C++] priority_queue(힙 응용) - 최대 수입 스케쥴

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

using namespace std;

struct Loc{
    int money;
    int date;
    
public:
    Loc(int money, int date){
        this->money = money;
        this->date = date;
    }
    
    bool operator<(const Loc &ref)const{
        return date>ref.date;
    }
};

int main() {
    int N,M,D,i,datemax=-2147000000,sum=0;
    priority_queue<int> pQ;
    vector<Loc> vec;
    
    scanf("%d",&N);
    
    for(i=0; i<N; i++){
        scanf("%d %d",&M,&D);
        vec.push_back(Loc(M,D));
        if(D > datemax) datemax = D;
    }
    sort(vec.begin(), vec.end());//날짜로 정렬 완료
    
    while(datemax != 0){   
        for(auto pos : vec){
            if(pos.date == datemax){
                //printf("%d",pos.money);
                pQ.push(pos.money);
            }
        }
        sum += pQ.top();
        pQ.pop();
        
        datemax--;
    }
    
    printf("%d",sum);
    return 0;
}

• 입력으로 한 쌍이 주어지며 각 요소를 정렬해야하는 문제이다.
• 따라서 구조체를 만들고 해당 구조체 템플릿의 벡터를 생성한다.
• 구조체에는 날짜만 정렬하겠다는 Operator가 선언되어 있기 때문에 Sort함수로 벡터를 정렬하면 날짜를 기준으로 벡터가 정렬된다.
• 날짜를 기준으로 선택해야지 최대 수입을 구할 수 있다. 왜냐하면 3일 이내로 해도되는 강연은 첫째날 둘째날 셋째날 모두 참여가 가능하지만 1일 이내로 해도되는 강연은 첫째날에만 참여가 가능하기 때문에, 일단 3일 이내로 최대한 액수가 큰 기업부터 선택하는 것이 유리하다.
• 따라서 일단 3일 짜리 기업의 액수를 priority queue에 넣고 top을 뽑아서 sum에 누적덧셈한다.
• 그 다음 2일짜리 기업의 액수를 priority queue에 넣는다. 이 priority queue에는 3일짜리도 들어있기 때문에 3,2일짜리 중 가장 액수가 큰 금액이 top에 뽑힐 것이다.
• 그 다음 1일짜리 기업의 액수를 priority queue에 넣는다. 이 priority queue에는 2,3일짜리도 들어있기 때문에 3,2,1일짜리 중 가장 액수가 큰 금액이 top에 뽑힐 것이다.

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/dashboard