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

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

import sys
import heapq

input = sys.stdin.readline

# 국회의원 선거를 조작
# 다솜이의 기계는 각 사람들이 누구를 찍을 지 미리 읽을 수 있다. 
# 어떤 사람이 누구를 찍을 지 정했으면, 반드시 선거때 그 사람을 찍는다.

# 형택구에 나온 국회의원 후보는 N명
# 다솜이는 이 기계를 이용해서 그 마을의 주민 M명의 마음을 모두 읽었다.

# 다솜이는 기호 1번
# 자신을 찍지 않으려는 사람을 돈으로 매수해서 국회의원에 당선이 되게 하려고 한다.
# 다른 모든 사람의 득표수 보다 많은 득표수를 가질 때, 그 사람이 국회의원에 당선

# 출력 : 다솜이가 매수해야하는 사람의 최솟값

N = int(input())

my_vote = int(input())

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

hq = []

answer = 0

for _ in range(N-1):
    heapq.heappush(hq,-int(input()))

while my_vote <= -hq[0]:
    
    maximum_vote = -heapq.heappop(hq)
    my_vote += 1
    heapq.heappush(hq,-(maximum_vote-1))
    answer += 1

print(answer)

 

이번 문제는 N명의 후보가 국회의원 선거에 나온다고 했을 때, 국회의원에 당선되기 위해 매수해야 하는 다른 지지자들의 최솟값을 구하는 문제이다.

 

가장 많은 득표 수를 얻기 위해서는 자신보다 크거나 같은 지지자들 중 가장 득표 수가 많은 지지자부터 매수해야 한다. (Greedy 알고리즘)

 

최댓값을 최대한 효율적으로 구하고 갱신하기 위해 우선순위 큐를 사용하는 Heap 자료구조를 사용했다.

 

그리디 알고리즘을 활용하여 풀 수 있는 간단한 문제였다 :)