[Python] 1417번 국회의원 선거

https://www.acmicpc.net/problem/1417

1417번: 국회의원 선거

---

 

22/09/17

 

 

실버 5를 순서대로 밀던 도중에 만난 문제로, 그다지 어렵지는 않았던 문제였다.

 

한번 틀리긴 했으나, 단순한 문제 읽고 구현하는 문제로, 쉽게 생각하면 되는 문제였다.

---

 

문제 접근 방식:

 

 

문제 주인공인 다솜이는 사람들을 매수해서 국회의원에 당선이 되게끔 하려 한다. 당선 조건은 다른 모든 후보들보다 많은 투표수를 가지는 것. 이때 매수하는 최소의 사람을 구하는 것이다.

 

나는 살짝 그리디 적인 접근을 했는데, 먼저 다솜이가 제일 우선적으로 매수해야 되는 사람은 후보들 중에서 제일 많은 표를 얻고 있는 후보의 지지자를 매수해야 된다고 생각했다.

왜냐하면, 우리는 어쨌든 다른 모든 후보들 보다 많은 투표수를 가져야 하므로, 제일 많은 투표수를 먼저 깎아내리는 것이 이득이기 때문이다.

 

때문에 반복문으로 현재 제일 많이 표를 가지고 있는 후보자를 1표 줄이고, 다솜이의 표를 1표 늘리는 방식으로 구현했다.

이후 만약에 다솜이가 다른 모든 후보들보다 더 많은 표를 가지고 있다면 종료하는 방식으로 진행했다.

 

얼마나 반복될지 모르므로 while문을 사용했으며, 다른 모든 후보들은 리스트 슬라이싱으로 구현했다.(다솜이가 첫 번째이므로)

 

혹시 몰라서, 만약 다솜이만 있는 경우를 예외처리를 해주었는데, 다솜이만 있다면 무조건 당선이므로 0을 출력하도록 코드를 짜두었다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 1417번 국회의원 선거
# 구현
n = int(input())
num_li = [int(input()) for _ in range(n)]
value = 0
if n != 1:
    while True:
        if num_li[0] > max(num_li[1:]):
            break
        else:
            num_li[0] += 1
            num_li[num_li[1:].index(max(num_li[1:]))+1] -= 1
            value += 1
print(value)