[백준/python] 1417번: 국회의원 선거

문제

https://www.acmicpc.net/problem/1417

1417번: 국회의원 선거

---

문제 요약

국회의원 선거에 N명의 국회의원 후보가 출마한다. 다솜이는 기호 1번이다.

 

기호 1번을 찍지 않은 사람들을 돈으로 매수해서 국회의원에 당선이 되게 하려고 할 때

 

다솜이가 매수해야하는 사람의 최솟값을 출력한다.

---

코드

from heapq import *

n = int(input())
# 국회의원 후보 수

val = int(input())
# 다솜이가 받은 득표 수

ans = 0
# 뺏어온 표 수

if n == 1:
# 다솜이 혼자 선거에 출마한 경우 예외 처리
    print(0)
    # 조작하지 않아도 당선
    exit()

hq = []

for i in range(1, n): 
    heappush(hq, -int(input()))
    # 다솜이를 제외한 후보들의 표 수를 음수로 삽입 (최대 힙을 구성하기 위해)
    # 파이썬에서 힙의 default가 최소 힙이기 때문

while val <= -hq[0]:
# 다솜이의 득표 수가 가장 많으면 종료 (-hp[0]은 가장 투표를 많이 받은 사람의 득표 수)
    x = heappop(hq)
    x += 1 
    # 가장 많이 투표를 받은 사람의 투표를 하나 빼서 (음수이므로 - 개념과 동일)

    val += 1 
    # 다솜이에게 전달

    ans += 1 

    heappush(hq, x)
    # 다시 변경된 x값을 삽입해서 힙 구성

print(ans)

---

코드 설명

1. 다솜이의 득표 수를 먼저 따로 입력 받고, 그 외 후보들의 표 수를 힙에 음수로 삽입한다.

+ Python에서 힙의 default이 최소 힙이므로 최대 힙을 구현하기 위해 음수로 삽입한다.

 

2. 다솜이 혼자 선거에 출마한 경우, 투표를 조작하지 않아도 당선되므로 0을 출력하고 종료한다.

 

3. 다솜이의 득표 수가 가장 많을 때까지 반복문을 실행한다.

 

3 - 1. heappop을 통해 가장 많이 투표를 받은 사람에게서 하나를 빼서 다솜이의 투표 수를 1 증가시킨다.

+ 음수 값을 힙에 저장했으므로 1을 더하는 것이 빼는 것과 같은 역할을 한다.

+ 다솜이의 투표 수를 증가시킬 때마다 결과 값을 1 증가시킨다.

 

4. 반복문이 종료되면, 결과 값을 출력하고 종료한다.