[BOJ][C++] 백준 2109번: 순회강연 (Gold III)

https://www.acmicpc.net/problem/2109

 

문제

한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다.
예를 들어 네 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d값이 차례로 2, 1, 2, 1 이라고 하자. 이럴 때에는 첫째 날에 4번 대학에서 강연을 하고, 둘째 날에 1번 대학에서 강연을 하면 80만큼의 돈을 벌 수 있다.

입력

첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 각 대학에서 제시한 p값과 d값이 주어진다.

출력

첫째 줄에 최대로 벌 수 있는 돈을 출력한다.

 

풀이

맨 뒤 스케줄부터 짠다고 생각하는게 포인트

 

특정 날짜를 기준으로

해당 날짜에 가능한 강연 (= 해당 날짜 < 강연 기한)들 중

가장 페이가 높은걸 그 특정 날짜에 배치한다

	    while(idx<n && v[idx].first>=day) {
	        pq.push(v[idx].second);
	        idx++;
	    }

 

해당 날짜에 가능한 날짜의 페이들을 우선순위 큐에 넣어놓고

	    if(pq.empty()) {
	        continue;
	    }
	    
	    sum += pq.top();
	    pq.pop();

 

가장 페이가 높은걸 (= pq.top()) 확정지음 (= sum+강연비)

 

그럼 pq에 남아있는 다른 강연들은 전부
지금 날짜보다 앞쪽인 날짜에서 당연히 가능한 강연들이다

(왜냐면 기한이 긴 순서대로 들어가고있으니까!)

 

그 다음(앞쪽) 날짜도 가능한 강연들의 페이를 우선순위큐에 넣고

그 중 가장 페이가 높은걸 그 날짜로 배치해서 수강료 챙기고

 

반복하면 끝

 

// 풀이 : https://whkakrkr.tistory.com

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

using namespace std;

typedef pair<int, int> ci;

const int INF = 10000;

bool cmp(ci a, ci b) {
    return a.first > b.first;
}

int main() {
    ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	
	int n;
	cin >> n;
	
	vector<ci>v(n);

	for(int i=0; i<n; i++) {
	    int p,d;
	    cin >> p >> d;
	    v[i] = {d,p};
	}
	
	sort(v.begin(), v.end(), cmp);
	
	int sum = 0, idx = 0;
	priority_queue<int> pq;
	
	for(int day=INF; day>0; day--) {
	    while(idx<n && v[idx].first>=day) {
	        pq.push(v[idx].second);
	        idx++;
	    }
	    
	    if(pq.empty()) {
	        continue;
	    }
	    
	    sum += pq.top();
	    pq.pop();
	}
	
	cout << sum;
	
    return 0;
}