[Python/파이썬] 백준 1417번: 국회의원 선거

문제

풀이

기호 1번을 제외한 나머지 표를 최대 힙에 넣는다.

힙을 pop()했을 때 나온 후보의 표가 기호 1번의 표보다 많다면, 그 후보를 한명 매수하고 다시 힙에 넣는다.

위 과정을 기호 1번의 표가 제일 많을 때까지 반복한다.

코드

import sys, heapq
input = sys.stdin.readline

n = int(input())
win = int(input())
nums = []

for _ in range(n - 1):
    num = int(input())
    heapq.heappush(nums, (-num, num))

cnt = 0
while nums:
    num = heapq.heappop(nums)[1]
    if num >= win:
        num -= 1
        win += 1
        cnt += 1
        heapq.heappush(nums, (-num, num))

print(cnt)

마무리

힙을 안다면 쉽게 풀 수 있는 문제.