[백준] 1417번: 국회의원 선거 - 파이썬

📎문제링크: https://www.acmicpc.net/problem/1417

1417번: 국회의원 선거

 

💼서론 

예~~전에 한번 봤다가 어케 푸는지 잘 모르겠어서 패스했던 문제다. 요즘 그리디 알고리즘을 배우고 있어서 다시 한번 도전해보았다. 구글링 없이 푸니까 나 자신 스스로도 성장했다고 느꼈다.

 

 

🧩문제 해석

다솜이는 국회의원이 되고 싶고 누가 누구를 뽑을지 알고 있다. 즉 다솜이 말고 다른 후보에게 투표하는 사람을 매수하여 자신을 투표하도록 만들어야 하는데 몇명을 매수해야 할까?ㅎ

 

 

📘풀이

1. 다솜이와 다른 후보들을 구분하여 입력받는다.
2. 후보들 가장 많이 득표하는 사람의 한 표를 뺏는다.
3. 2번 과정을 다솜이가 가장 많이 득표할때까지 반복한다.

 

 

풀이 중 2번을 한번에 처리하려고, 즉 한표씩 뺏는게 아니라 빼앗아야 하는 표를 계산하여 한번에 뺏기위해 (max(candi) - dasom) // 2 + 1로 시도하였다. 하지만 이렇게 되면 1번 테스트케이스에서 걸린다. 왜냐? 최대득표자가 둘 이상이 있을때는 한명한테서만 뺏는것보다 여럿한테서 한표씩 뜯어내는게 이득이기 때문이다. 그래서 그냥 1표씩 뺏는 방법으로 택했다.

 

 

국회의원 선거