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

그리드 알고리즘

풀이

그때그때 데이터의 최대 값을 구한 이후에 다솜(temp)와 비교하고 temp보다 같거나 크다면 최대값을 1 줄이고 다솜(temp)를 1 늘리는 방식으로 계속 찾아나가면 됨.

import sys

# sys.stdin = open("input.text", "rt")

N = int(input())
data = []
for i in range(N):
    data.append(int(input()))

temp = data[0]
count = 0
while True:
    if len(data) == 1:  #본인만
        break
    max_data = max(data[1:])
    if max_data >= temp:  
        for i in range(1, len(data)):
            if data[i] == max_data:
                data[i] -=1 
                temp += 1
                count += 1
                break
    if temp > max(data[1:]):
        break

print(count)

다른 코드

import sys

sys.stdin = open("input.text", "rt")

N = int(input())
dasom = int(input())
data = []
for i in range(N-1):
    data.append(int(input()))

count = 0
data.sort(reverse=True)
if N == 1:  #다솜 혼자
    print(0)
else:
    while data[0] >= dasom:
        dasom +=1
        data[0] -=1
        count +=1
        data.sort(reverse=True)
    print(count)

계속해서 내림차순 정렬을 통해 최대값을 낮추는 형식. 가독성이 더 좋음.