2109 - 순회강연

문제

코드

#include<bits/stdc++.h>
using namespace std;

priority_queue<int, vector<int>, greater<int>> pq;
vector<pair<int,int>>v;
int n,d,p,ret;

int main(){
	cin >> n;
	
	 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++){
	 	pq.push(v[i].second);
	 	if(pq.size() > v[i].first) pq.pop();
	 }
	 while(pq.size())ret += pq.top(), pq.pop();
	 cout << ret << '\n';
}

풀이

위 그림처럼 하루에 강연 하나만 가능하기에 priority_queue의 크기가 day보다 크면 오름차순의 pq를 pop시킨다. 즉 작은게 빠져나가고 큰 것만 남게 된다는 것이다.
주어진 day만큼 과정을 반복한다.

결과

후기

처음 생각했던 방법은 날짜에서 최댓값을 하나씩 뽑는거였다.
2일차에 1일차보다 pay가 높은 강연이 2개라면 1일차 2일차 모두 day가 2인 강연을 갈 것이라는 반례를 생각 못했던 것이다.
그리디 관련 문제를 풀면 항상 오답이 발생하는데 조금 더 신중하게 반례를 생각해서 한 번에 맞출 수 있도록 노력해봐야겠다.