[백준] 1417 국회의원 선거 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/1417
• 그리디, 최대 힙 사용

 

from heapq import heapify

n = int(input())
dasom = int(input())
heap = [-int(input()) for _ in range(n-1)]  # 최대 힙 구현을 위해 -를 붙여 저장
cnt = 0

heapify(heap)

if n == 1:
    print(0)
    exit()

while dasom <= -heap[0]:    # 최대 득표수가 다솜이보다 작아질 때 까지 반복함 (-를 붙여 양수로 변환)
    heap[0] += 1    # 최대 득표수가 음수로 저장되있기 때문에 1증가
    dasom += 1      # 다솜이 득표수 증가
    cnt += 1
    heapify(heap)   # 힙의 내용이 바뀌었기 때문에 다시 정의 (재정렬)

print(cnt)