백준 12018. Yonsei TOTO

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

12018번: Yonsei TOTO

 

각 과목의, 각 사람이 넣은 마일리지를 내림차순으로 정렬하면 성준이는 수강인원번째의 마일리지 만큼 넣으면 그 과목을 수강할수 있다.

(마일리지가 같다면 성준이에게 우선순위가 있으므로)

 

예를들어 다음 과목은 

5 4

36 25 1 36 36

 

내림차순 정렬하면 다음과 같게 된다

5 4

36 36 36 25 1

 

수강가능 인원이 4명이므로 4번째인 25만큼 성준이가 마일리지를 투자하면 수강할수 있게 된다.

 

예외적으로 수강신청인원이 수강가능인원보다 적으면 무조건 수강가능하므로 1만 투자하면된다. (마일리지는 한 과목에 1에서 36까지 투자 가능)

 

이렇게 각 과목을 듣기 위해 필요한 최소 마일리지를 모두 구하고 

그 값들을 오름차순 정렬해서, 작은수부터 보유 마일리지가 넘지 않을때까지 더해가면서 카운트한다.

 

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

int n, m;

int main()
{
    cin >> n >> m;
    vector<int> ans;

    while(n--)
    {
        // 신청수, 수강인원
        int p,l;
        cin >> p >> l;

        vector<int> v;
        for(int i = 0; i < p; i++)
        {
            int num;
            cin >> num;
            v.push_back(num);
        }

        // 신청수보다 수강인원이 많으면 마일리지를 최소인 1만 넣으면된다
        if(p < l)
        {
            ans.push_back(1);
            continue;
        }

        // 마일리지 기준 내림차순 정렬
        sort(v.begin(), v.end(), greater<>());

        // l-1번째 만큼 마일리지를 넣으면 수강신청 가능
        ans.push_back(v[l-1]);

    }


    // 필요 마일리지 기준 오름차순 정렬
    sort(ans.begin(), ans.end(), less<>());

    // 보유 마일리지 내에서 몇개의 과목 수강신청 가능한지 탐색
    int sum = 0, cnt = 0;
    for(int i = 0; i < ans.size(); i++)
    {
        sum += ans[i];
        if(sum > m)
            break;
        cnt++;
    }

    cout << cnt;
}