백준 1781 C++

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

이 문제의 중요한 생각도 가장 큰 날짜에서 날짜를 하나씩 줄여가며 처리할 수 있는 문제를 뽑으면 된다.

그렇게 어렵게 느껴지진 않았다.

 

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll result;
int n;		//문제 수
vector<pair<int, int>> v;		//데드라인, 컵라면 수 -> 데드라인은 N이하의 자연수이다.
priority_queue<int> pq;		//cup이 큰 순으로 들어갈 pq이다.
priority_queue<pair<int, int>> dcpq;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;

	int d, c;		//deadline, cup
	for (int i = 0; i < n; i++) {
		cin >> d >> c;
		dcpq.push({ d, c });		//이러면 d가 큰 순& c가 큰 순으로 들어간다.
		//v.push_back({ d,c });
	}

	//sort(v.begin(), v.end());		//deadline이 작은순 & cup이 작은 순 -> ? 데드라인이 긴 순으로 해야하는거 아닌가? - 그래야 데드라인이 길면 7일에 할 수 있는 것끼리 들어가고 6일차가 되어도 7일꺼가 들어가있으면 풀 수 있으니까.
	
	//int endDay = v[n - 1].first;		//가장 늦은 데드라인일 것이다.

	//하루가 지나면 하나씩 뽑아야한다.
	for (int i = dcpq.top().first; i > 0; i--) {		//데드라인 날짜가 가장 큰 것에서 계속 낮아지는 걸 i--로 함.
		while (dcpq.size() && dcpq.top().first == i) {		//dcpq에 있는 가장 많은 데드라인이 i와 동일하다면
			pq.push(dcpq.top().second);
			dcpq.pop();
		}

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

	cout << result;
}