[백준 2109번 / C++] 순회강연

처음에 이 문제를 접근할 때 이런식으로 접근 하였다. 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int check[10001];
int sum;
bool cmp(pair<int, int>p1, pair<int, int>p2) {
	return p1.first > p2.first;
}
int main() {
	int n; cin >> n;
	int p, d;
	vector <pair<int, int>> v;
	for (int i = 0; i < n; i++) {
		cin >> p >> d;
		v.push_back({ p,d });
	}
	sort(v.begin(), v.end(), cmp); //p값의 내림차순 
	for (int i = 0; i < n; i++) {
		int index = v[i].second;
		if (check[index] == 0) {
			sum += v[i].first;
			check[index] = 1;
		}
		else {
			for (int j = index - 1; j >= 1; j--) {
				if (check[j] == 0) {
					check[j] = 1;
					sum += v[i].first;
					break;
				}
			}
		}
	}
	cout << sum;
}

먼저 강연료의 오름차순대로 정렬 한 뒤 해당 날짜를 가리키는 배열이 비어있다면 check 를 해주고 없을 경우 해당 배열 인덱스에서부터 0까지 돌아보면서 비어있는 공간이 생기면 그 인덱스 위치에 check를 해주는 것이다. 해당 풀이법으로 테스트를 통과할 순 있지만 최적의 방법은 아니라고 판단하여 다른 방법을 찾아보았다. 

 

---

 

 

<priority_queue> 자료구조

 

먼저 강연료와 날짜를 정렬 시킬 때 날짜를 기준으로 오름차순으로 정렬 하였다.

그리고 min heap 구조로 Priority_Queue를 생성하여 데이터가 삽입될 때마다 제일 최소값이 루프노드에 위치하게 된다. 

이것을 활용하여 예제를  한번 살펴보자.

 

date가 1일인 강연료가 2와 20이 있다. 

priority_Queue에 하나씩 넣게 되는데 제일 작은 값이 루프노드에 위치하니 그 값을 pop() 해주기만 하면된다. 

그렇게 되면 date가 1인 강의 중 강의료가 2인것은 나가버리고 강의료가 20인 강의가 위치하게 된다. 이후 date가 2이고 강의료가 8과 100이 들어오는데 이때 8이 루프노드로 위치하게 되고 20가 80은 그의 자식노드로 위치하게 된다. 이런식으로 반복하게 되면 결국 최소값이 다 사라진 최대값들로 이루어진 하나의 트리가 만들어지고 트리의 해당 노드들을 모두 더하게 되면 그것이 최대로 받을 수 있는 강의료의 최댓값이라는 것을 알 수 있다. 

 

이때 Priority_Queue의 사이즈는 해당 날짜보다 클 수 없다는 것을 명심하자.

즉, date가 3인 데이터를 돌아볼때는 Queue 의 사이즈는 당연 3이하여야한다. 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std; 
int main() {	
	int n; cin >> n; 
	vector <pair<int, int>> v; 
	priority_queue <int, vector<int>, greater<int>> q; //우선순위 큐.min heap
	int p, d; 
	for (int i = 0; i < n; i++) {
		cin >> p >> d; 
		v.push_back({ d,p }); 
	}
	sort(v.begin(), v.end()); //날짜 오름차순대로 정렬
	for (int i = 0; i < n; i++) {
		q.push(v[i].second);  
		if (q.size() > v[i].first) {
			q.pop(); 
		}
	}
	int sum = 0; 
	while (!q.empty()) {
		sum += q.top(); 
		q.pop(); 
	}
	cout << sum; 
}

 

2109번: 순회강연