[BAEKJOON] 1781 컵라면 (C++)

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

1781번: 컵라면

문제

그리디에서 꽤 자주 나오는 패턴의 문제이다.

데드라인이 정해진 과제를 수행하여 최대 이득을 얻을 수 있는 경우를 구하는 문제

 

 

풀이

가장 먼저 떠오르는 방법은 

가장 큰 이득을 주는 과제부터 수행할 수 있는 경우 수행하는 것이다.

수행할 때 해당 과제 데드라인의 가장 마지막날에 수행한다고 가정하면 최대 이득을 보장한다.

ex) 데드라인이 5인 과제는 5일에 수행한다.

 

두번째로는 데드라인이 빠른 날짜 순서로 확인하고 처리하는 방법이 있다.

원리는 다음과 같다.

일단 수행한다고 가정한다.

해당 데드라인보다 이미 수행했다고 가정한 과제가 많은 경우(수행할 수 없는 과제들까지 포함한 것)

보상값이 적은 것부터 다시 제거한다.

예를들어, 데드라인 3, 보상값이 10인 과제를 처리할 때 우선순위 큐에 이미 들어있는 값이 3개이상이라면 3개까지 줄여줘야한다. 이때 우선순위 큐의 가장 위에 있는 값은 이미 처리한(처리했다고 가정한)과제들 중 보상값이 가장 작은 경우이므로 제거해주면 된다.

 

두번째 방법으로 코드를 작성하였다.

 

코드

#include <bits/stdc++.h>

#define endl "\n"

using namespace std;

int N;
vector<pair<int, int>> P;
priority_queue<int> PQ;
void Input() {
	cin >> N;
	int d, c;
	for (int i = 0; i < N; i++) {
		cin >> d >> c;
		P.push_back({ d,c });
	}
}

void Solve() {
	int ans = 0;
	sort(P.begin(), P.end());
	for (int i = 0; i < P.size(); i++) {
		ans += P[i].second;
		PQ.push(-P[i].second);
		while (PQ.size() > P[i].first) {
			ans += PQ.top(); PQ.pop();
		}
	}
	cout << ans;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	//freopen("input.txt", "r", stdin);
	Input();
	Solve();
	return 0;
}