[Level 4] 한국코드페어 - 외주

출처 : https://level.goorm.io/exam/49104/%EC%99%B8%EC%A3%BC/quiz/1

외주

형기는 뛰어난 개발 실력을 가지고 있지만 게을러서 아직 일자리를 구하지 못했다. 사실 집에서 뒹굴거리는 게 더 좋아서 구할 생각도 없는 듯하다. 그러던 어느 날, 형기는 슬슬 새 컴퓨터를 장만해야겠다고 생각이 들었고 그러려면 돈이 필요하다는 것을 깨달았다. 어쩔 수 없이 형기는 외주작업을 맡아 함으로써 돈을 벌고자 한다. 형기는 외주 전문 사이트에 글을 올린 후, 그대로 잠이 들었다.

다음 날 일어나서 자신이 올린 글을 확인해보니 수많은 외주작업 요청이 들어온 것을 보고는 입이 쩍 벌어졌다. 벌써부터 돈이 굴러들어오는 생각에 입꼬리가 올라갔지만, 각 외주작업의 요청에는 계약금과 마감기한이 정해져 있어 신중하게 골라야만 했다. 아무리 형기의 개발 실력이 뛰어나도 이 수많은 외주작업을 해내기엔 벅찬 일이었기 때문이다.

자세한 상황은 다음과 같다. 형기에게 들어온 외주작업 요청의 수는 N개이다. 각 외주작업은 계약금 M와 마감기한 D를 가지고 있다. 형기는 어떤 외주작업이든지 끝마치는 데 하루가 소요된다. 이러한 상황에서 형기는 최대한 많은 돈을 벌 수 있도록 외주작업을 선택하고자 한다. 형기가 벌 수 있는 최대 금액은 얼마일까?

 

입력

첫째 줄에 형기에게 들어온 외주작업 요청의 수를 나타내는 정수 N이 주어진다. (단, 1<=N<=200,000)

이후 N개의 줄에 걸쳐서 각 줄마다 두 개의 정수 Mi, Di가 공백으로 구분되어 주어진다. 

Mi는 i번째 외주작업을 완료했을 때 받는 금액, Di는 i번째 외주작업의 데드라인이다. (단, 1<=Mi,Di<=200,000)

또한, 현 시점을 1일째로 기준을 잡는다. 즉, 오늘이 지나고 나면 데드라인이 1인 외주작업을 더 이상 완료할 수 없다.

출력

형기가 벌 수 있는 최대의 금액을 출력한다.

예시 4

입력

15
821
4611
9510
159
311
38
535
1911
1912
936
6314
464
687
797
554

출력

733

---

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;

int main() {
	int N;
	cin >> N;

	vector<pair<int, int>> work(N);

	int M, D;
	for (int i = 0; i < N; i++) {
		cin >> M >> D;
		work[i].first = D;
		work[i].second = M;
	}

	sort(work.begin(), work.end());
	reverse(work.begin(), work.end());

	int idx = 0;
	int currentDay = work[0].first;
	map<int, int> selectMoney;
	priority_queue<pair<int, int>> spare;

	while (idx < N) {
		int popDay = work[idx].first;
		int popMoney = work[idx].second;
		// 아직 기간 남았고 묵혀뒀던 일이 있으면
		if (currentDay > popDay && spare.size() != 0) {
			selectMoney[currentDay] = spare.top().first;
			spare.pop();
			currentDay -= 1;
			continue;
		}
		// 오늘 할 일
		if (selectMoney[popDay] < popMoney) {
			if (spare.size() != 0 && spare.top().first > popMoney) {
				selectMoney[popDay] = spare.top().first;
				spare.pop();
				spare.push({ popMoney, popDay });
			}
			else {
				selectMoney[popDay] = popMoney;
			}
			currentDay = popDay - 1;
		}
		else {
			spare.push({ popMoney, popDay });
		}
		idx += 1;
	}

	while (spare.size() != 0 && currentDay > 0) {
		if (selectMoney[currentDay] == 0) {
			selectMoney[currentDay] = spare.top().first;
			spare.pop();
		}
		currentDay -= 1;
	}

	long long sum = 0;
	for (const auto& elem : selectMoney) {
		sum += elem.second;
	}

	cout << sum;

	return 0;
}