[C++] 백준 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값이 주어진다.

출력

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

 

먼저 날짜가 빠른 순서로 정렬 후 날짜가 같을 경우 페이가 많은 순으로 정렬해보자.

이게 최적해일까?

아래의 테스트 케이스의 경우 날짜가 빠른 강의부터 순서대로 하는 것보다 날짜가 느린 강의를 먼저하는 것이 더 많은 페이를 받을 수도 있다.

Test case
3
1 1
10 2
10 2

 

여기서 이 문제를 푸는데 필요한 자료구조가 있다.

Priority_queue란?

큐의 한 종류로 우선순위 큐라고 하며, 각 요소가 우선순위가 연관되고 우선순위에 따라 요소가 제공된다. 즉 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다.

 

사용 방법

선언

priority_queue <T, Container, Compare> 변수명;

기본적으로 높은 숫자부터 내림차순으로 정렬되며

Container에는 배열, T에는 배열의 타입, Compare은 오름차순인지 내림차순인지 결정할 수 있다.

priority_queue <int, vector<int>, greater<int>> pq;	//오름차순
priority_queue <int, vector<int>, less<int>> pq;	//내림차순

기본적인 사용 방법은 큐와 동일하다.

 

우선순위 큐를 사용하여 다시 풀어보자.

이번에는 기한이 빠른 순서로 정렬 후 같은 날짜라면 페이가 작은 순서로 정렬한다.

우선순위 큐에 페이를 push 후 pq.size 와 남은 기한을 비교하며 큐의 최솟값을 지워나간다.

큐의 사이즈가 기한보다 크면 같은 기한을 둔 강연이 2개 이상있다는 뜻이다.

( pq.size() > v[i].first )

큐에 오름차순으로 정렬되어 들어가므로 있으므로 top에 있는 값을 버린다.

큐의 사이즈가 기한보다 크므로 top의 값을 pop해준다.

따라서 최대로 벌 수 있는 돈은 185이다.

 

코드

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

using namespace std;

priority_queue<int, vector<int>, greater<int> > pq;
vector<pair<int, int>>v;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);

	int n;
	cin >> n;
	
	int a, b;
	for (int i = 0; i < n; i++) {
		cin >> b >> a;
		v.push_back({ a,b });
	}

	sort(v.begin(), v.end());

	int res=0;
	for (int i = 0; i < v.size(); i++) {
		res += v[i].second;
		pq.push(v[i].second);

		if (pq.size() > v[i].first) {
			res -= pq.top();
			pq.pop();
		}
	}
	cout << res;
	return 0;
}