백준 1417 국회의원 선거

문제

• 다솜이가 사람들을 매수해서, 다른 국회의원의 표 수보다 크게 만들기
• 사람을 매수하면, 해당 국회의원의 표 수는 -1이 되고, 다솜이의 표 수 는 +1이 된다.
• 다솜이의 표 수가 다른 국회의원 표 수보다 크면, 그렇게 되기까지 매수한 사람 수를 구하기

풀이과정

• 우선순위 큐 사용
• 최대값을 뽑는 우선순위 큐를 사용함
• pop한 값이 국회의원의 표 수가 다솜이보다 크면 -1 하고 push
• 다솜이보다 작으면 pop으로 끝

배운점

• heapq 에서 최대값을 뽑도로 하려면, 입력받는 값에 음수를 취함으로써 간단하게 구현이 가능하다.

시행착오

• 국회의원들의 표 수를 큰 순서로 정렬해서 순회하며
• 국회의원이 다솜이보다 표 수가 높고, 다음 국회의원보다 표 수가 작거나 같아질 때까지 다솜이 +1, 국회의원 -1 을 했다.
  • 뒤 쪽 국회의원에 의해 다솜이의 표 수가 더 높아지면, 앞의 국회의원에서 덜 빼도 되기 때문에 틀리다.
• 반례

  4
  0
  1
  1
  0

import sys
import heapq


input = sys.stdin.readline
N = int(input())

dasom = int(input())
others = []
for _ in range(N-1):
    heapq.heappush(others, -int(input()))
ans = 0
while others:
    other = -heapq.heappop(others)
    if other >= dasom:
        heapq.heappush(others, -(other-1))
        dasom += 1
        ans += 1
print(ans)