백준 1417번 - 국회의원 선거

국회의원 선거 문제 바로 가기

풀이 날짜: 2026-01-20

baekjoon 알고리즘 문제 풀이

풀이 코드


import sys
input = sys.stdin.readline
import heapq

heap = []
n = int(input())
dasom = int(input())

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

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

count = 0

while True:
    top = -heap[0]

    if dasom > top:
        break
    heapq.heappop(heap)
    top-=1
    dasom+=1
    count+=1
    heapq.heappush(heap, -top)
print(count)

문제 접근

이 문제는 다솜이를 제외한 다른 후보들의 득표 수가 주어졌을 때, 다솜이가 단독 1등이 되기 위해 필요한 최소 매수 횟수를 구하는 문제다. 한 번 매수할 때마다 다솜의 표는 1 증가하고, 어떤 한 후보의 표는 1 감소한다. 중요한 점은 항상 가장 표가 많은 경쟁자를 대상으로 매수하는 것이 최적이라는 것이다.

입력 처리와 예외 케이스

후보가 1명뿐인 경우(n == 1)에는 다솜이 이미 1등이므로 매수할 필요가 없다. 이 경우를 처리하지 않으면 힙이 비어 있는 상태에서 접근하게 되어 런타임 에러가 발생한다. 따라서 이 경우에는 바로 0을 출력하고 프로그램을 종료해야 한다.

힙에 데이터를 넣는 방식

다솜을 제외한 후보들의 득표 수를 힙에 저장할 때는 -x 형태로 넣는다. 이렇게 하면 최소 힙에서 가장 작은 값인 -x가 곧 원래 값 기준 최대 득표 후보가 된다.

heapq.heappush(heap, -x)

다솜이 단독 1등이 될 때까지 매수 반복하기 (while True)

다솜의 표가 (top = -heap[0]) 이 값보다 커지는 순간, 다솜은 단독 1등이 되므로 반복을 종료한다.

매수 과정

가장 표가 많은 후보를 힙에서 제거한다. heapq.heappop(heap)
그 후보의 표를 1 감소시킨다. top -= 1
다솜의 표를 1 증가시킨다. dasom += 1
매수 횟수를 1 증가시킨다. count += 1
감소된 후보를 다시 힙에 넣는다. heapq.heappush(heap, -top)

Vienna sausage