BOJ 23757 - 아이들과 선물 상자 (Python)

S2, 우선순위 큐

문제

상훈이는 $N$개의 선물 상자를 가지고 있다. 선물 상자에는 현재 담겨있는 선물의 개수가 적혀있다.

선물을 받을 아이들이 $M$명 있다. 아이들은 각자 $1$에서 $M$까지의 서로 다른 번호를 하나씩 부여받았다.

$1$번 아이부터 $M$번 아이까지 한 번에 한 명씩, 현재 선물이 가장 많이 담겨있는 상자에서 각자 원하는 만큼 선물을 가져간다. 이 때, 앞서 누군가 선물을 가져갔던 선물 상자에서 또다시 가져가도 상관없다.

하지만 상자에 자신이 원하는 것보다 적은 개수의 선물이 들어있다면, 선물을 가져가지 못해 실망한다.

상훈이는 한 명이라도 실망하지 않고 모두가 선물을 가져갈 수 있는지 궁금하다.

풀이

• 최대힙을 통한 우선순위 큐를 구성
• 최대값이 현재 아이가 가지고 싶은 선물의 수보다 작으면 종료

from sys import stdin
import heapq
n, m = map(int, stdin.readline().split())
boxes = list(map(int, stdin.readline().split()))
kids = list(map(int, stdin.readline().split()))
boxQ = []

for box in boxes:
    heapq.heappush(boxQ, -box)

for kid in kids:
    value = -heapq.heappop(boxQ)
    if value < kid:
        print(0)
        exit()
    value -= kid
    heapq.heappush(boxQ, -value)

print(1)