BOJ 2109 - 순회강연

www.acmicpc.net/problem/2109

2109번: 순회강연

 

이 문제는 이전에 풀었던, 컵라면 (백준 1781) 문제와 보석도둑 (백준 1202) 문제 하고 비슷한 양상을 보인다.

 

문제에서 제시한 D 값을 일종의 데드라인으로 볼 수 있고,

하루 하루 날짜가 경과하면서, 데드라인 날짜를 넘어가지 않는 경우라면, 최대힙에 넣어서 최댓값 P 를 찾아낼 수 있도록 탐색해준다.

 

컵라면 (백준 1781) 문제를 풀때 처럼 데드라인을 기준으로 최대값을 세지 않도록 주의해야한다 

(하루씩 경과하는 날짜에 따라서 그 날짜가 데드라인 안에 있을경우, 최대힙에 넣어서 추려내는 방식을 써야된다는게 핵심임)

 

다만 이 문제에서는 컵라면 문제와는 다르게, 

입력받은 데드라인을 내림차순 정렬하고 날짜를 최대날짜에서 부터 하나씩 줄여가면서

해당 날짜가 데드라인 안에 포함되면 최대힙에 넣고

그렇지 않을땐, 힙이 비어 있지 않다면 하나씩 빼서 답을 추가해준다.

 

- C++

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
int N, P, D, answer;
vector<pair<int, int>> vec; // D, P 순서  
 
bool comp(pair<int, int>& p1, pair<int, int>& p2) {
    return p1.first > p2.first;
}
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N;
    
    int max_day = -1;
    for (int i = 0; i < N; ++i) {
        cin >> P >> D;
        vec.push_back({D, P});
        max_day = max(max_day, vec[i].first);
    }
    
    sort(vec.begin(), vec.end(), comp);
         
    priority_queue<int> pq;
 
    int idx = 0; 
    for (int day = max_day; day >= 1; --day) {
        while(idx < N && day <= vec[idx].first) {
            pq.push(vec[idx].second);
            idx++;
        }
        
        if (!pq.empty()) {
            answer += pq.top();
            pq.pop();
        }
    }
    
    cout << answer;
        
    return 0;
}