[우선순위 큐] 순회 강연 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만큼의 돈을 벌 수 있다.

 

 

풀이

1. 그리디 알고리즘

- 현재 날짜에서, 가능한 높은 pay 가 높은 강의를 고른다.

 

2. 우선순위 큐를 활용한 구현

2-0. 받은 강의의 값들을 날짜 기준 내림차순으로 정렬한다.

2-1. 10,000 일부터 1일까지 아래와 같이 순회한다.

2-2. i 는 10,000 부터 1까지 날짜를 순회한다. index 는 lectures 를 0 부터 n - 1까지 순회한다.

이때, i 와 day 가 일치하는 lectures 의 pay 를 모두 우선순위 큐에 넣어준다.

그 후, 우선순위 큐의 top 을 답에 더해준다.

풀이코드

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
using namespace std;
// 2109 순회 강연

struct Lecture{
	int pay, day;
};

// 날짜 내림차순 정렬
bool cmp(const Lecture &u, Lecture &v){
	return u.day > v.day;
}

int main(){
	int n;
	 cin >> n;
	vector<Lecture> lectures(n);
	
	for(int i=0; i <n; i++){
		cin >> lectures[i].pay >> lectures[i].day;
	}
	
	sort(lectures.begin(), lectures.end(), cmp);
	
	int index = 0;
	priority_queue<int> q;
	int ans = 0;
	
	for(int i = 10000; i >=1 ; i--){
		// i 일까지 할 수 있는 강의를 후보로 넣어주는 부분
		// 우선순위 큐에 넣었으므로, i 일까지 할 수 있는 강의들 중 top 이 최고 pay 를 주는 강의이다		
		while(index < n && lectures[index].day == i){
			q.push(lectures[index].pay);
			index += 1;
		}
		
		// i 일에 어떤 강연을 할지 결정하는 부분
		// 우선순위 큐가 비지 않았다면, 최대값을 더한다.
		if(!q.empty()){
			ans += q.top();
			q.pop();
		}
	}
	cout << ans << endl;
}

 

---

퇴고

1. 문제를 잘 읽자.

- 처음 문제를 읽었을 때, 해당 일에만 해당 강연을 할 수 있는줄 알고 시간 낭비를 했었다.