Axolotl

BOJ 13904 과제

21 Dec 2024
PS Algorithm

우선순위큐로 그리디하게 입력 값을 처리하는 문제입니다. 과제 마감 기한을 우선순위 큐의 크기와 비교하며 우선순위 큐에 들어간 가장 작은 점수의 과제와 계속해서 교체해주면 됩니다.

BOJ 2109 순회강연 문제와 똑같은 문제입니다.

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

using namespace std; 

using pii = pair<int, int>;

int N, d, w;
int ans = 0; 
priority_queue<int, vector<int>, greater<int>> pq; 
vector<pii> v; 

int main() {
    cin >> N;
    v.resize(N); 
    
    for(int i = 0; i < N; i++) {
        cin >> d >> w; 
        v[i].first = d; 
        v[i].second = w; 
    }
    
    sort(v.begin(), v.end()); 
    
    for(int i = 0; i < N; i++) {
        if(pq.size() < v[i].first) {
            pq.push(v[i].second); 
        }
        else {
            if(pq.top() < v[i].second) {
                pq.pop(); 
                pq.push(v[i].second); 
            }
        }
    }

    while(!pq.empty()) {
        ans += pq.top();
        pq.pop(); 
    }

    cout << ans; 
}