12018 - Yonsei TOTO

연세대학교 수강신청이 얼마 전부터 바뀌어, 마일리지 제도로 바뀌었다. 이 제도는 각각의 학생들에게 마일리지를 주어 듣고 싶은 과목에 마일리지를 과목당 1~36을 분배한다. 그리고 모두 분배가 끝이 나면 과목에 대해서 마일리지를 많이 투자한 순으로 그 과목의 수강인원만큼 신청되는 방식이다.

성준이는 연세대학교 재학 중인 학생이다. 성준이는 저번 수강신청에서 실패하여 휴학을 했기 때문에 이번 수강신청만은 필사적으로 성공하려고 한다. 그래서 성준이는 학교 홈페이지를 뚫어버렸다.

그 덕분에 다른 사람들이 신청한 마일리지를 볼 수 있게 되었다. 성준이는 주어진 마일리지로 최대한 많은 과목을 신청하고 싶어 한다. (내가 마일리지를 넣고 이후에 과목을 신청하는 사람은 없다) 마일리지는 한 과목에 1에서 36까지 넣을 수 있다.

C++

1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5  ios::sync_with_stdio(0);
6  cin.tie(0);
7  int n, m;
8  cin >> n >> m;
9  priority_queue<int, vector<int>, greater<int>> q;
10
11  for(int i=0; i<n; ++i) {
12    vector<int> t;
13    int p, l;
14    cin >> p >> l;
15
16    for(int i=0; i<p; ++i) {
17      int v;
18      cin >> v;
19      t.push_back(v);
20    }
21
22    if(p < l) {
23      q.push(1);
24      continue;
25    }
26
27    sort(t.rbegin(), t.rend());
28    q.push(t[l-1]);
29  }
30
31  int cnt = 0;
32  while(true) {
33    if(cnt >= n) break;
34    int min = q.top();
35    if(min > m) break;
36    q.pop();
37    m -= min;
38    ++cnt;
39  }
40
41  cout << cnt << endl;
42  return 0;
43}