[Python] 1417번 국회의원 선거

✏️ 문제

 

문제 파악

득표수 배열을 A로 가정하자.

 

처음엔 if max(A) > A[0] 이라는 조건문이 true면 최댓값을 가지고 있는 후보의 득표수를 -1 하고 A[0]에 득표수 +1, 매수해야 하는 사람수 +1 하는 방향으로 코드를 짰다.

이렇게 짜니 무한루프를 돌고 있었고 생각해보니 다솜이가 원하는 A[0]이 배열의 최댓값이 되면 A[0]의 값이 계속 -1, +1, -1, +1 을 반복하게 되기 때문이었다.

 

그래서 max(A) == A[0] 라는 조건문을 사용하여 코드를 새로 짜니 해결되었다.

또한 최대 득표수를 가지고 있는 후보에 A[0]가 있으면서 (and) 여러 후보라면 1명만 매수하면 되므로 매수해야 하는 사람을 +1 해주었다.

 

알고리즘

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

 

 

코드

n = int(input())
people = 0
candidate = []

for i in range(n):
  candidate.append(int(input()))

while True:
  best = max(candidate)
  if best != candidate[0]: 
    candidate[candidate.index(best)] -= 1
    people += 1
    candidate[0] += 1
  else:
    if candidate.count(best) != 1:
      people += 1
    break

print(people)