백준 1417번
https://www.acmicpc.net/problem/1417

문제

후기

⏰ 풀이시간 20분 ++⏰

그리디로 간단하게 풀 수 있는 문제였다.

다솜이의 표가 후보중 표를 가장 많이 가지고 있는 사람보다 많아지면 되는 문제다.

후보의 수가 1이면 표를 살 필요 없으며, 이미 다솜이의 표가 제일 많아도 살 필요 없다.

위의 예외사항을 적용하여 간단하게 구현할 수 있었다.

나의 풀이

import sys
input= sys.stdin.readline

N= int(input())
k= int(input()) #다솜이의 표
li= [] #득표자들의 표
cnt = 0 #몇표를 샀는지

if N == 1: #후보의 수가 1이면
    print(0) #표를 살 필요없다.
    exit()

for _ in range(N-1): #다솜이 보다 표가 많은 득표자의 표만 list에 담아놓는다.
    num = int(input())
    if num>=k:
        li.append(num)

if len(li)==0: #이미 다솜이의 표가 제일 많아도
    print(0) #표를 살 필요없다.
    exit()

li.sort(reverse=True)

while True:
    if k>li[0]: #다솜이가 후보중 제일 표가 많은사람보다 많다면
        print(cnt) #표를 더 살필요 없으므로 종료
        exit()
    li[0] -=1 #후보중 표가 제일많은 후보의 표 1표 감소
    k+=1 # 다솜이의 표 1표 증가
    cnt +=1 # 1표를 샀다
    li.sort(reverse=True) #후보의 표 내림차순 정렬