12018번 Yonsei TOTO

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

boj 복습 생각 그리디 탐욕

우선 각 수강 과목에 넣은 마일리지를 내림차순 정렬을 한다.

이후에 수강 인원을 고려하여 그 과목을 수강할  수 있는 최소의 마일리지를 구한다.

구한 마일리지들을 다시 오름차순 정렬을 한다.

그 이후로 주어진 마일리지(m)을 활용하여 Greedy하게 답을 구해준다.

처음 제출했을 때 틀렸었는데, 45 ~ 47번 째 줄처럼 작성했었다.

생각해보니 L이 마일리지 신청한 인원보다 클 때는 성준이가 무조건 수강할 수 있으므로

최소의 마일리지인 1을 부여한다.

#include<bits/stdc++.h>
 
using namespace std;
 
#define Max 111
 
int n, m, t[Max];
vector<vector<int> > v;
 
bool cmp(const int & a, const int & b) 
{
    return a > b;
}
 
int main() 
{
    scanf("%d %d", &n, &m);
 
    int P, L;
    for (int i = 0; i < n; i++) {
        /*
        P : 각 과목에 신청한 사람 수
        L : 과목의 수강 인원
        */
        scanf("%d %d", &P, &L);
 
        int input;
        vector<int> temp;
 
        for (int j = 0; j < P; j++) {
            scanf("%d", &input);
            temp.push_back(input);
        }
        
        // 내림차순
        sort(temp.begin(), temp.end(), cmp);
 
        // L값 범위 고려
        if (L > temp.size()) {
            t[i] = 1;
            continue;
        }
 
        /*
        if (L > temp.size()) {
            L = temp.size();
        }
        */
 
        // 수강할 수 있는 마일리지 최솟값(수강 인원 고려)
        t[i] = temp[L - 1];
    }
 
    // 오름차순
    sort(t, t + n);
 
    int answer = 0;
    for (int i = 0; i < n; i++) {
        if (m - t[i] < 0) {
            break;
        }
        m -= t[i];
        ++answer;
    }
 
    printf("%d\n", answer);
 
    return 0;
}