백준 12018 Yonsei TOTO 파이썬

www.acmicpc.net/problem/12018

12018번: Yonsei TOTO

import heapq

ans = 0
n, m = map(int, input().split())
temp = []

for _ in range(n):
    P, L = map(int, input().split())
    mileages = list(map(int, input().split()))
    heapq.heapify(mileages)
    num = L - P
    # 수강미달인 과목
    if num > 0:
        heapq.heappush(temp, 1)
    else:
        for i in range(abs(num)):
            heapq.heappop(mileages)
        # 수강가능한 마일리지 중 가장 낮은 마일리지 (점수가 동일하다면 성준이에게 우선순위가 있기때문)    
        heapq.heappush(temp, heapq.heappop(mileages))

while temp:
    mileage = heapq.heappop(temp)
    if m - mileage >= 0:
        ans+=1
        m-= mileage
    else:
        break

print(ans) 

# 5 76
# 5 4 
# 36 25 1 36 36
# 4 4
# 30 24 25 20
# 6 4
# 36 36 36 36 36 36
# 2 4
# 3 7
# 5 4
# 27 15 26 8 14
    

실력이 약간 늘었나보다. 

그 어떤것도 보지 않고 혼자의 힘만으로 문제를 풀어나가는 횟수가 늘고있고 핵심아이디어를 생각하는데까지 시간이 짧아지고 있다.

이 문제 역시 보자마자, '엇 이거 우선순위큐 쓰면 될거같은데...' 라고 생각하고 one try 만에 성공했다.

구현도 그리 어렵지 않았다.

각 과목별 다른 수강신청자들의 마일리지 현황을 우선순위큐로 만들고나서

과목의 수강인원 보다 신청인이 적은경우, 즉 수강신청이 미달인 경우, 1 마일리지만 사용해도 된다. 1 마일리지를 우선순위 큐에 담는다.

그리고 미달이 아닌 경우는,

다른 수강신청자들의 마일리지를 우선순위큐로 만들었기 때문에 초과한 인원이 있다면 초과한 인원만큼은 제거해주고 

턱걸이로 수강신청에 성공한 마지막 사람을 heap에서 꺼내서 내가 신청할 마일리지 우선순위 큐에 저장한다.

이 과정을 반복한 후,

이 문제는 최대 과목 신청 가능한 수만 알아내면 되기 때문에

내가 신청할 마일리지 우선순위큐를 순회하면서 현재 내가 소유한 마일리지로 신청 가능하면 과목수를 추가하고 마일리지에서 신청한 과목 마일리지 를 빼준다.