백준 1417 국회의원 선거

문제 URL :https://www.acmicpc.net/problem/1417

1417번: 국회의원 선거

문제 접근법 : 

내가가지고 있는 득표수에서 최대값에서 하나씩 빼가서 최대값보다 더커질때까지 여러번 반복합니다.

그반복횟수를 출력해주면됩니다.

득표수나 n이 너무 적기때문에 효율적인 알고리즘이 아니어도 최대값을 하나씩 빼서 최대값보다 크면 

반복문에서 빠져나오는 알고리즘이면 좋을것같습니다.

 

저는 pq를 바로 생각해서 파이썬으로 풀게 됐네요

 

소스코드:

import sys
import heapq
input = sys.stdin.readline
n = int(input().rstrip())
l = [int(input().rstrip()) for i in range(n)]
pq = [-l[i] for i in range(1,n)]
heapq.heapify(pq)
res = 0
while pq and l[0]<=-pq[0]:
    l[0]+=1
    t = heapq.heappop(pq)
    heapq.heappush(pq,t+1)
    res+=1
print(res)

궁금한점 혹은 모르는 점 어떤질문이든 댓글은 언제나 환영입니다.