문제

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

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

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

코드

import sys, heapq

input = sys.stdin.readline
n, mile = map(int, input().split())
heap = list()
heapq.heapify(heap)
cnt = 0

for i in range(n):
    p, d = map(int, input().split())
    miles = list(map(int, input().split()))
    miles.sort(reverse=True)

    if p < d:
        mile -= 1
        if mile < 0:
            break
        cnt += 1

        continue

    while len(miles) > d:
        miles.pop()

    heapq.heappush(heap, miles.pop())

while len(heap) > 0:
    m = heapq.heappop(heap)
    if mile - m >= 0:
        mile -= m
        cnt += 1
    else:
        break

print(cnt)

설명

수강신청을 한 인원보다 수강제한 인원이 적은 경우는 1마일리지를 써서 수강신청을 한다. 아닐 경우는 수강신청을 한 인원중에 마일리지를 적게 써서 수강신청에 실패하는 사람들은 모두 제외 시키고 수강신청이 성공하는 사람들 중 가장 적은 마일리지를 쓰는 사람과 같은 마일리지를 사용한다. (같은 마일리지면 성준이에게 우선순위가 있기 때문) 최소힙으로 가장 작은 마일리지부터 pop해가며 힙이 비어있거나 마일리지가 적어 더이상 신청을 할 수 없을 때까지 반복한다.