BOJ 12018 - Yonsei TOTO

문제 링크

각 과목별로 수강에 필요한 마일리지를 구한다.
이때 정원보다 신청 인원이 적은 경우에는 1마일리지만 사용해도 된다.
장원보다 신청인원이 많은 경우에는 신청인원 중 가장 적은 마일리지로 듣는 사람의 자리를 빼앗아야 한다.
마일리지가 같으면 내가 우선권을 가지니까 신청인원 중 가장 적은 마일리지로 듣는 사람의 마일리지만큼을 넣으면 가장 적은 마일리지로 해당 과목을 들을 수 있다.

과목별 필요한 마일리지들을 정렬하고 낮은 것부터 낮은 것부터 고른다.

import sys


def read():
    return sys.stdin.readline().rstrip()


n, m = map(int, read().split())
needs = []
for _ in range(n):
    p, l = map(int, read().split())
    mileages = list(map(int, read().split()))

    if p < l:
        needs.append(1)
        continue

    mileages.sort(reverse=True)
    needs.append(mileages[l-1])

needs.sort()
count = 0
used_mileage = 0
for need in needs:
    if used_mileage + need > m:
        break
    used_mileage += need
    count += 1

print(count)