[C++] 백준 알고리즘 12018 Yonsei TOTO

12018

다른 사람들이 신청한 마일리지를 temp라는 최소 힙으로 담았다.

 

만약 3명만 수강신청 가능할 때, 5명이 신청을 했다고 해보자

마일리지를 5 10 15 20 25를 담았다고 치면 이를 최소 힙 temp 에 담아서 정렬한다.

그리고 내가 신청을 하기 위해, 오버된 만큼을 힙에서 pop 시킨다.

5-3, 즉 2만큼 pop해보자

15, 20, 25 만 남았다!

 

같은 마일리지를 할당해도 내가 우선시 되므로

15, 20, 25 할당된 수업에서 내가 수강신청하려면 15만 할당해도 된다.

---

[결론]

 

1. 인원이 널널하면 마일리지를 1만 할당, 최소힙 q에 1을 담는다.

 

2. 5명 신청가능한데 5명이 신청한 경우,

최소힙temp에 5명의 마일리지를 넣어서, 최소 마일리지 넣은 애를 구하고,

최소 만큼만 내가 할당한다.

내가 할당할 마일리지는 최소힙 q에 담는다.

 

3. 수강 인원이 오버한 경우, 오버한 사람이 몇 명인지 구하고 그만큼 temp에서 pop해준다.

이후 2번과 같은 방법으로 할당해야하는 마일리지를 구해서 q에 담는다.

---

q에는 내가 할당해야할 마일리지가 담겨있다.

예를들면 5 15 25 35 45 이런식으로.

내가 가진 마일리지가 50이면 나는 3개의 수업만 신청 가능하다.

(5+15+25 =45 이므로 최대 3개 신청)

 

최대한 많이 신청하려면 마일리지가 작은 수업부터 신청하면된다 (q를 최소힙으로 한 이유!!)

 

즉, q의 맨 처음 요소부터 my_m 이라는 변수에 더해주고

더할 때 마다 total (총 신청가능한 수업 수)을 ++ 해주고

my_m이 내가 가진 마일리지보다 커지면 total을 계산하지 않는다!

 

#include<iostream>
#include<queue>

using namespace std;

int main() {
	priority_queue<int,vector<int>,greater<int>> q; // 내가 사용해야할 마일리지 담기
	
	int n, m;
	cin >> n >> m;

	while (n--) {
		priority_queue<int, vector<int>, greater<int>> temp; //한 과목당 다른 사람이 신청한 마일리지 담기 ex) 36 25 1 36 36
		
		//p는 수강신청한 사람, l은 수강가능인원
		int p, l;
		cin >> p >> l;
		int p_temp = p;

		//다른사람이 이 과목에 할당한 마일리지를 최소힙에 담기
		while (p_temp--) {
			int i;
			cin >> i;
			temp.push(i);
		}

		//자리가 여유롭다면 마일리지 1만 할당
		if (l > p)
			q.push(1);

		//정원이 다 찼다면, 제일 적게 할당한 사람 만큼만 할당하면 된다
		else if (l == p)
			q.push(temp.top());

		//5명 가능인데 7명이 신청할 경우,
		//오버한 만큼(2명)을 카운트하고, 그만큼 pop해준다
		//7명 중 2명 커트했고, 제일 적게 마일리지 넣은 사람만큼(5번째 사람)
		//내가 마일리지를 넣으면 수강신청 성공!
		else {
			int over = p - l;
			while ((over)--) {
				temp.pop();
			}
			q.push(temp.top());
		}
	}
	
	int total = 0;
	int my_m = 0;
	while (!q.empty()) {
		my_m += q.top();
		q.pop();
		if(my_m <= m) total++;
	}
	cout << total << '\n';
}