99클럽 코테 스터디 24일차 TIL + 우선순위 큐

문제

Baekjoon1417: 국회의원 선거

• 설명: 다른 후보의 지지자를 최소한으로 빼앗아 다솜이를 당선되게 하라.

풀이

• 그리디하게 지지자가 가장 많은 후보자의 지지자를 빼앗아 다솜이가 당선되는 순간이 답이다.
• 우선순위 큐에 다솜이를 제외한 후보자들의 지지자수를 넣고, 지지자가 가장 많은 후보의 지지자를 빼앗는다.
  • 만약 지지자가 없다면 큐에 넣지 않는다.

오늘의 회고

• 해커톤 화이팅

Code

# Baekjoon01417.py
from queue import PriorityQueue

n = int(input())

dasom = int(input())

pq = PriorityQueue()
for _ in range(n - 1):
    temp = int(input())
    pq.put((-temp, temp))

ans = 0
while pq.qsize():
    _, top = pq.get()
    if dasom > top:
        break

    ans += 1
    dasom += 1
    if top >= 2:
        pq.put((-(top - 1), (top - 1)))

print(ans)