[BOJ/2109] 순회 강연, c++

www.acmicpc.net/problem/2109

2109번: 순회강연

한줄 후기 : 골 4 맞어?!

 

하루에 하나만 강연 할 수 있을 때 pay를 가장 많이 받을 수 있는 방법을 찾으면 된다.

처음에 우선순위 큐인걸 알고 바로 짰다가 예외 케이스를 간과해서 틀렸다.

예외 케이스는

3

10 2

10 2

3 1

 

이러면 13이 아니라 20이 답이다. 

왜냐면 2일안에 할 수 있는 강연은 1일날 해도 되니까 정답은 10+10 = 20 이다.

 

//AC
//BOJ 2109 순회강연
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, int> lec;

bool cmp(const lec &a, const lec &b){
	if(a.second == b.second){
			return a.first<b.first;
		}
		else{
			return a.second<b.second;
		}
}
priority_queue<int> pq;
vector<lec> day;
int main(){
	int n, p, d, ans = 0, cur = 0, idx;
	cin >> n;
	for(int i=0; i<n; i++){
		scanf("%d %d", &p, &d);
		day.push_back({p, d});
		cur = max(cur, d);
	}
	sort(day.begin(), day.end(), cmp);
	idx = n-1;
	while(cur){
		while(idx < n && day[idx].second == cur){
			pq.push(day[idx--].first);
		}
		if(!pq.empty()){
			ans += pq.top();
			pq.pop();
		}
		cur-=1;
	}
	cout << ans;
	return 0;
}

먼저 벡터에 pay, day를 받고, 이를 정렬해 주는데 day가 큰 것부터 정렬해준다.

첫 cur 가 가장 day가 큰 값이된다. 

이제 그 cur랑 day가 같은 값들은 모두 큐에 넣어준다. 그리고 큐에 있는 값들을 ans에 더해준다.

cur은 1씩 줄여 나간다.

그러면 cur이 0보다 작거나 같아질 경우 할 수 있는 모든 강연을 큐에 담은 것이고, ans에는 그 pay들의 총합이 담겨 있다.

 

 

너무 어렵다... 나도 day가 큰 것부터 정렬 하는 건 생각 했는데 그 이후가 너무 어려워서 찾아봤다.

아직 갈길이 멀다.. 그리디 어려워