[백준/BOJ] 백준 9869번 : Milk Scheduling

https://www.acmicpc.net/problem/9869

9869번: Milk Scheduling

 

가장 뒤 날짜부터, 마감 날짜가 해당 날짜 이상인 소들 중 가장 많이 우유를 만들 수 있는 소를 고르는 방법으로 문제를 해결했다. 가장 뒤 날짜부터 고르면 이전에 우선순위 큐(가장 많은 우유를 만드는 게 먼저 나오는 우선순위 큐)에 넣어 놨던 소들이 앞에 날짜에서 사용될 수 있다.

 

코드

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

int n;
vector<pair<int, int>> cow; //(마감시간, 만들 수 있는 우유)
int max_day = 0;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++) {
		int gi, di;
		cin >> gi >> di;
		cow.push_back(make_pair(di, gi));
		max_day = max(max_day, di);
	}

	//마감 날짜 기준으로 정렬
	sort(cow.begin(), cow.end());
	int cow_index = cow.size() - 1;

	//날짜를 거꾸로 확인하면서 마감날짜 day일때, 마감날짜가 day 이상인 소들 중 가장 많이 우유를 만들 수 있는 소를 고른다
	int result = 0;
	priority_queue<int> pq;
	for (int day = max_day; day >= 1; day--) {

		while (cow_index >= 0) {
			if (cow[cow_index].first >= day) {
				pq.push(cow[cow_index].second);
				cow_index--;
			}
			else {
				break;
			}
		}

		if (!pq.empty()) {
			result += pq.top();
			pq.pop();
		}
	}

	cout << result;

	return 0;
}