99클럽 코테 스터디 16일차 TIL Boj 17503. 맥주 축제

Approach

• 특정 개수에 대한 최솟값을 보자마자 우선순위 큐를 생각했었다.
• 입력 크기를 생각했을 때 투포인터 방식으로도 해결할 수 있을 것 같은데, 일단 구현이 쉬운 우선순위 큐로 구현하고자 했다.
• 도수로 정렬한 뒤, N개 만큼 힙에 넣고 선호도보다 크면 하나 빼는 방식으로 구현하였다.

---

Solution 💡

import sys
from heapq import heappop, heappush

N, M, K = map(int, sys.stdin.readline().split())

lst = [list(map(int, sys.stdin.readline().split())) for _ in range(K)]
hq = []

lst.sort(key=lambda x: x[1])
preference = 0
level = -1

for pre, lv in lst:
    preference += pre
    heappush(hq, pre)

    if len(hq) > N:
        a = heappop(hq)
        preference -= a
    
    if len(hq) == N and preference >= M:
        level = lv
        break

    
print(level)