백준 12018 : Yonsei TOTO

www.acmicpc.net/problem/12018

12018번: Yonsei TOTO

수강신청을 할 때 제한된 마일리지를 가지고 다른 학우들과 경쟁해서 최대한 많은 수업을 수강해야 하는 문제이다. 이미 다른 학생들이 각 수업에 사용한 마일리지의 양을 알고 있고, 마일리지가 같을 시 문제의 주인공에게 우선순위가 주어진다. 따라서 각각의 수업에 학생들이 사용한 마일리지를 배열로 받아 정렬한 후 제한 인원의 마지막에 걸리는 사람의 마일리지를 그대로 배팅하게 되면 최소한의 비용으로 수업을 들을 수 있다.

각각의 수업에 대하여 그 수업을 들을 때 필요한 최소 비용을 식별하여 우선순위 큐에 넣어주고 우선순위 큐에서 소모 포인트가 가장 적은 것부터 하나씩 꺼내면서 수강하면 최대한 많은 수업을 수강할 수 있다.

#include <iostream>
#include <queue>
#include <algorithm>

#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

int point_arr[101];

int main() {
	fastio;
	int subject_num, point, ans = 0;
	int student_num, limit;
	priority_queue<int> pq;

	cin >> subject_num >> point;
	while (subject_num--) {
		cin >> student_num >> limit;
		for (int i = 0; i < student_num; i++) cin >> point_arr[i];

		if (student_num < limit) {
			pq.push(-1); continue;
		}
		
		sort(point_arr, point_arr + student_num, greater<int>());
		pq.push(-point_arr[limit - 1]);
	}

	while (!pq.empty()) {
		if ((point += pq.top()) < 0) break;
		ans++; pq.pop();
	}
	cout << ans;

	return 0;
}

 

메모리: 2016 KB

시간: 0 ms