[BOJ] 12018번 Yonsei TOTO (C++)

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

12018번: Yonsei TOTO

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int n, m, num, p, l;
	cin >> n >> m;
  
	vector<int> vv;
	for(int i = 0; i < n; i++){
		cin >> p >> l;
		vector<int> v;
		for(int j = 0; j < p; j++){
			cin >> num;
			v.push_back(num);
		}
		sort(v.begin(), v.end(), greater<>());
		if(v.size() < l) vv.push_back(1);
		else vv.push_back(v[l - 1]);
	}
  
	sort(vv.begin(), vv.end());
  
	int i = 0;
	for(i = 0; i < vv.size(); i++){
		m -= vv[i];
		if(m < 0) break;
	}
	cout << i << endl;
	return 0;
}

최대한 많은 과목을 신청하려면 각 과목을 최대한 적은 마일리지로 투자해야 한다.

 

5명이 신청했고, 수강인원이 4명인 과목에 다른 학생이 36 25 1 36 36의 마일리지를 넣은 상태인 경우

36 36 36 25 1 (내림차순)으로 정렬하고 적어도 4등 안에 들어야 한다.

즉, 적어도 25 이상 넣어야 함을 의미한다. 따라서 25를 넣으면 이 과목을 수강할 수 있다.

 

간과했던 부분은 각 과목에 최소 1 이상의 마일리지를 넣어야 한다는 것이다. 따라서 각 과목에 신청한 사람 수가 과목의 수강인원보다 적으면 1을 넣어야 한다.