BAEKJOON #1417) 국회의원 선거 (python)

알고리즘 분류: 구현, 그리디, 시뮬레이션

 

1417번: 국회의원 선거

 

💡풀이

n = int(input())
votes = []
cnt = 0

for _ in range(n):
    votes.append(int(input()))

while votes.index(max(votes)) != 0:
    votes[votes.index(max(votes))] -= 1
    votes[0] += 1
    cnt += 1

for i in range(1, n):
    if votes[0] == votes[i]:
        votes[i] -= 1
        votes[0] += 1
        cnt += 1
print(cnt)

 

• 이 문제의 로직은 간단하다. "표를 가장 많이 가지고 있는 애의 표를 뺏어오자"이다.
• 다솜이의 득표 수가 votes 리스트의 모든 원소들 중에서 최댓값이 되기 전까지 while문을 반복한다.
• while문 안에서는 로직대로 제일 많은 애의 표는 하나 감소시키고, 다솜이의 표(0번 원소)는 하나 증가시키고 카운트(매수한 표의 개수)도 하나 증가시킨다.  
• for문은 최댓값이 중복되는 경우를 방지하기 위하여 수행한다.

 

처음에는 for문을 추가하지 않고 제출했더니 '틀렸습니다' 떴다. 진짜 그으으으대로 구현만 했는데, 왜 틀렸지 생각해봤는데, 문제는 max()함수에 있었다. 중복된 최댓값이 있어도 제일 앞에 있는 최댓값만을 반환해주는 함수이기 때문!

예를 들면, for문 없이 입력을 하면 출력이 다음처럼 나온다.

이렇게 7, 7, 7, 4에서 끝나버린다. 중복된 값이 있지만, 중복된 7도 최댓값으로 취급하는 것이다.

 

그래서 아래처럼 for문을 추가하여주면,

다솜이'만' 진짜 최대 투표 수를 갖게 되어 제대로 된 정담 '6'을 출력할 수 있다.