[🥈2 / 백준 23757 / 파이썬] 아이들과 선물 상자

 

 

 

23757번: 아이들과 선물 상자

 

문제

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

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

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

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

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

입력

첫째 줄에 선물 상자의 수 N 과 아이들의 수 M이 공백을 사이에 두고 주어진다. (1≤M≤N≤10⁵)

둘째 줄에 각 선물 상자에 들어있는 선물의 개수 c₁,c₂,…,c_N이 공백을 사이에 두고 주어진다. (1≤c_i≤10⁵)

셋째 줄에 아이들의 번호 순으로 각 아이가 원하는 선물의 개수 w₁,w₂,…,w_M이 공백을 사이에 두고 주어진다. (1≤w_i≤10⁵)

출력

모든 아이들이 실망하지 않고 각자 원하는 만큼 선물을 가져갈 수 있으면 1을, 그렇지 않으면 0을 출력한다.

 

예제 입력 1 4 4 4 3 2 1 3 1 2 1	예제 출력 1 1
예제 입력 2 4 3 4 3 2 1 3 1 5	예제 출력 2 0

 

풀이

 

"현재 선물이 가장 많이 담겨있는 상자에서" 라는 구문에서 알 수 있듯, 최대 힙을 이용하여 해결해야 한다.

파이썬의 heapq 모듈은 최소 힙을 기준으로 정렬이 되므로, 각 선물값에 음수를 곱하여 사용한다.

아이들은 순서대로 적힌 만큼 가져가므로, 정렬을 해선 안 된다.

 

import sys, heapq
input = sys.stdin.readline

n,m = map(int,input().split())
c = [-i for i in map(int,input().split())] # 각 원소에 음수를 곱한다
heapq.heapify(c) # 힙 정렬
w = list(map(int,input().split()))

for i in w:
    if not c:
        print(0)
        break
    diff = -heapq.heappop(c) - i
    if diff < 0:
        print(0)
        break
    elif diff > 0:
        heapq.heappush(c, -diff)
else:
    print(1)