수강신청을 할 때 제한된 마일리지를 가지고 다른 학우들과 경쟁해서 최대한 많은 수업을 수강해야 하는 문제이다. 이미 다른 학생들이 각 수업에 사용한 마일리지의 양을 알고 있고, 마일리지가 같을 시 문제의 주인공에게 우선순위가 주어진다. 따라서 각각의 수업에 학생들이 사용한 마일리지를 배열로 받아 정렬한 후 제한 인원의 마지막에 걸리는 사람의 마일리지를 그대로 배팅하게 되면 최소한의 비용으로 수업을 들을 수 있다.
각각의 수업에 대하여 그 수업을 들을 때 필요한 최소 비용을 식별하여 우선순위 큐에 넣어주고 우선순위 큐에서 소모 포인트가 가장 적은 것부터 하나씩 꺼내면서 수강하면 최대한 많은 수업을 수강할 수 있다.
#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 |
'컴퓨터 사이언스 > 1고리즘' 카테고리의 다른 글
백준 13325 : 이진 트리 (0) | 2021.03.17 |
---|---|
백준 2660 : 회장뽑기 (4) | 2021.03.17 |
백준 9322 : 철벽 보안 알고리즘 (0) | 2021.03.10 |
백준 4375 : 1 (1) | 2021.03.10 |
백준 3896 : 소수 사이 순열 (0) | 2021.03.10 |