백준 BOJ 1417 국회의원 선거

문제

 

코드

import sys
import heapq

input = sys.stdin.readline

n = int(input())
votes = [int(input()) for _ in range(n)]

dasom = votes[0]
heap = [-x for x in votes[1:]]
heapq.heapify(heap)

cnt = 0

while heap and dasom <= -heap[0]:
    top = -heapq.heappop(heap)
    
    top -= 1
    dasom += 1

    heapq.heappush(heap, -top)
    cnt += 1

print(cnt)

 

다솜이가 1번 후보이고, 나머지 후보들이 존재한다. 다솜이가 당선되려면 다른 모든 후보들의 표 보다 다솜이의 표가 커야 한다.

그러니 매수는 항상 현재 표가 가장 많은 후보의 지지자에게 해야한다.

 

한 번 매수 시

그 후보 표 -1
다솜 표 +1

 

따라서 다음과 같은 흐름으로 코드를 완성해야 한다.

가장 표 많은 후보를 찾는다
그 후보 표를 1 줄인다
다솜 표를 1 늘린다
이걸 다솜이 1등이 될 때까지 반복한다

 

이때, 파이썬의 heapq는 기본이 최소힙이기에 가장 작은 값이 나온다. 따라서 가장 큰 값이 필요하므로 음수로 넣는다.

votes = [5, 7, 7, 3]

dasom = votes[0]          # 5
heap = [-7, -7, -3]       # 나머지 후보를 음수로 저장

 

음수로 저장하면 실제 가장 큰 7이 -7이 되고, 힙에서는 -7이 -3보다 작으니까 먼저 나오게 된다. 따라서 최소 힙을 최대 힙처럼 사용한다.

 

 

-heap[0]은 현재 다른 후보 중 최다 득표 수이다. 

heap[0]는 -7 이므로 마이너스를 달아서 최다 득표 수 7로 만들어 준다.

while heap and dasom <= -heap[0]:

 

이는 다솜의 표가 현재 1등 후보 표 보다 작거나 같으면 계속 매수하라는 뜻이다.

 

이후 현재 제일 표 많은 후보를 꺼낸다.

top = -heapq.heappop(heap)

 

그 후보 표를 1개 줄이고 다솜 표를 1개 늘린다.

top -= 1
dasom += 1

 

줄어든 후보를 다시 힙에 넣어 다른 후보자보다 표가 많을 수도 있는 점을 대비한다.

heapq.heappush(heap, -top)