백준 1417 - 국회의원 선거

문제

알고리즘 분류)

• 구현
• 자료구조
• 그리디 알고리즘
• 시뮬레이션
• 우선순위 큐

풀이

이번 문제의 핵심은 [①,②,③,④ .... N] 중
① 의 값을 나머지 값들중에서 빼앗아와 나머지 모든 값들보다 커지는 '최소' 시점을 찾으면 된다
반복문을 줄이기 위해 어떤 수학적인 규칙을 찾기위하여 수십분 고민했지만 결국 찾지못해
1씩 증가하거나 감소시켜 반복문을 구현했다

선택한 알고리즘)
[②,③,④ .... N] 중 가장 큰 값이 ① 보다 작아질 때 까지 가장 큰 값을 1씩 감소, ①을 1씩 증가 시켜주었다
배열을 그때그때 내림차순 정렬하여 0번째 값을 감소시키는 것 보다
max(배열)의 값을 찾는게 시간복잡도가 조금이나마 적을 것 같다고 생각했다

소스코드

python)

import sys
N = int(input())
array=[]
cnt=0
for i in range(N):
    if i!=0:
        array.append(int(sys.stdin.readline()))
    else:
        num=int(input())
        
while array and max(array)>=num:
    array[array.index(max(array))]-=1
    num+=1
    cnt+=1
print(cnt)