C++[백준]1781번 컵라면

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

1781번: 컵라면

 

솔루션

---

처음에 데드라인이 가장 늦게 끝나는 것 부터 채워 오다가 시간초과를 받았다.

 

그래서 떠 올린 방법이 우선순위 큐 2개를 이용해서 푸는 방법이다

 

아직 처리 안한 문제를 담은 pq1

 - 데드라인이 빠른 것 부터, 같다면 컵라면 수를 많이 주는 것부터

 

내가 처리한 문제들을 담은 pq2

 - 컵라면의 개수가 가장 낮은 것부터 (이때 deadline은 상관 없을 것 같다.)

 

 

for문을 i를 통해서 1일부터 N일 까지 돌게 되는데,

 pq1에서 i일이 데드라인일 때, 컵라면 개수를 많이 주는 것을 pq2로 담아주고 pq1에서 뽑아준다.

 이를 pq2의 사이즈가 i가 될 때 까지 반복한다.(pq2의 개수는 1일에 1문제를 할 수 있으므로 사이즈만큼 더 할 수 있다)

 

 그리고 pq1에서 아직 현재 날짜의 데드라인인 문제가 남아있다면

   pq2의 컵라면수가 가장 낮은 것보다 pq1의 컵라면 수가 더 많이 준다면

   pq2의 컵라면수를 빼 주고, pq1의 컵라면 수를 더해준다.

 

 그리고 해당 데드라인까지 처리 못한 작업이 pq1에 남아있는데 이를 다 뽑아준다.

 

 

 

코드

---

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

struct pa {
	int deadline, cnt;
	//데드라인이 낮은 것 부터 pq.top에 오도록
	bool operator<(const struct pa& t) const {
		//같으면 cnt가 큰 것이 오도록
		if (deadline == t.deadline) {
			return cnt < t.cnt;
		}
		return deadline > t.deadline;
	}
};

//이미 처리한 일
struct work {
	int deadline, cnt;
	//cnt가 가장 낮은 것이 top에 오도록
	bool operator<(const struct work& t) const {
		if (cnt == t.cnt) {
			//deadline은 상관 없음
			return deadline < t.deadline;
		}
		return cnt > t.cnt;
	}
};

int N;
priority_queue<struct pa> pq;
priority_queue<struct work> pq2;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;

	for (int i = 0; i < N; i++) {
		int dead, cnt;
		cin >> dead >> cnt;
		pq.push({ dead,cnt });
	}

	int ans = 0;
	for (int i = 1; i <= N; i++) {
		//데드라인날인데, 그 앞에 처리한 일이 현재 날짜보다 개수가 작을 때,
		while (!pq.empty() && pq2.size() < i && pq.top().deadline <= i) {
			ans += pq.top().cnt;
			pq2.push({ pq.top().deadline,pq.top().cnt });
			pq.pop();
		}

		//데드라인이 더 늦는데, 더 많은 양을 얻을 수 있을 때.
		while (!pq.empty() && !pq2.empty() && pq2.top().cnt < pq.top().cnt && pq.top().deadline <= i) {
			ans -= pq2.top().cnt;
			pq2.pop();
			ans += pq.top().cnt;
			pq2.push({ pq.top().deadline,pq.top().cnt });
			pq.pop();
		}

		while (!pq.empty() && pq.top().deadline == i) pq.pop();
	}
	cout << ans << "\n";
}