[그리디] 코딩테스트 문제 TIL (국회의원 선거) - 백준 1417번

1. 오늘의 학습 키워드

• 그리디
• 힙
• 우선순위 큐

---

2. 문제: 1417. 국회의원 선거

• 단계: 🥈 실버 5단계
• 주제:
  • 구현
  • 자료 구조
  • 그리디 알고리즘
  • 시뮬레이션
  • 우선순위 큐
• 출처: https://www.acmicpc.net/problem/1417

문제

다솜이는 사람의 마음을 읽을 수 있는 기계를 가지고 있다. 다솜이는 이 기계를 이용해서 2008년 4월 9일 국회의원 선거를 조작하려고 한다.

다솜이의 기계는 각 사람들이 누구를 찍을 지 미리 읽을 수 있다. 어떤 사람이 누구를 찍을 지 정했으면, 반드시 선거때 그 사람을 찍는다.

현재 형택구에 나온 국회의원 후보는 N명이다. 다솜이는 이 기계를 이용해서 그 마을의 주민 M명의 마음을 모두 읽었다.

다솜이는 기호 1번이다. 다솜이는 사람들의 마음을 읽어서 자신을 찍지 않으려는 사람을 돈으로 매수해서 국회의원에 당선이 되게 하려고 한다. 다른 모든 사람의 득표수 보다 많은 득표수를 가질 때, 그 사람이 국회의원에 당선된다.

예를 들어서, 마음을 읽은 결과 기호 1번이 5표, 기호 2번이 7표, 기호 3번이 7표 라고 한다면, 다솜이는 2번 후보를 찍으려고 하던 사람 1명과, 3번 후보를 찍으려고 하던 사람 1명을 돈으로 매수하면, 국회의원에 당선이 된다.

돈으로 매수한 사람은 반드시 다솜이를 찍는다고 가정한다.

다솜이가 매수해야하는 사람의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 후보의 수 N이 주어진다. 둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 이렇게 총 N개의 줄에 걸쳐 입력이 들어온다. N은 50보다 작거나 같은 자연수이고, 득표수는 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 다솜이가 매수해야 하는 사람의 최솟값을 출력한다.

예제 입력 1

3
5
7
7

예제 출력 1

2

예제 입력 2

4
10
10
10
10

예제 출력 2

1

예제 입력 3

1
1

예제 출력 3

0

예제 입력 4 

5
5
10
7
3
8

예제 출력 4

4

---

3. 문제 풀이

Step1. 문제 이해하기

이 문제는 다솜이(기호 1번)가 국회의원에 당선되기 위해 다른 후보를 찍으려는 사람들을 매수하여 최소한의 노력으로 승리하려는 문제입니다.

문제의 핵심은 기호 1번의 득표수가 나머지 모든 후보의 득표수보다 많아지도록 하는 최소 매수 인원을 계산하는 것입니다.

입출력을 살펴보도록 하겠습니다.

• Input:
  • 첫째 줄에 후보의 수 N이 주어집니다.
    • N은 50이하의 자연수입니다.
  • 둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 이렇게 총 N개의 줄에 걸쳐 입력이 들어옵니다.
• Output:
  • 첫째 줄에 다솜이가 매수해야 하는 사람의 최솟값을 출력합니다.

Step2. 문제 분석하기

현재 다솜이의 득표수는 고정되어 있습니다.

다른 후보들의 득표수를 매수하여 다솜이의 득표수가 올라갸아 합니다.

매수해야 하는 사람의 최솟값을 구하기 위해서는, 가장 득표수가 많은 후보부터 매수합니다. 왜냐하면, 가장 득표수가 높은 후보를 매수하는 것이 효율적으로 전체 차이를 줄이는 방법이기 때문입니다.

매수 과정은 다음과 같습니다:

• 가장 득표수가 높은 후보를 매수하여 해당 후보의 득표수를 줄이고, 다솜이의 득표수를 증가시킵니다.
  • 해당 후보자에게 투표한 사람들 중 1명만 매수하는것이 아니기 때문에, 매번 정렬을 해야 합니다. 하지만 힙 자료구조를 사용한다면 해결할 수 있습니다.
• 이 과정을 반복하며, 다솜이의 득표수가 나머지 모든 후뵤의 득표수보다 많아질 때 종료합니다.

Step3. 코드 설계

• 입력으로 후보의 수 N과 각 후보의 득표수를 받습니다.
• 다솜이(기호 1번)의 득표수를 dasom 으로 저장하고, 나머지 후보들의 득표수를 리스트 others에 저장합니다.
• 다음 과정을 반복합니다:
  • others 리스트에서 가장 큰 득표수를 가진 후보를 선택합니다.
  • 해당 후보의 득표수를 1 감소시키고, 다솜이의 득표수를 1 증가시킵니다.
  • 매수 횟수를 1 증가시킵니다.
• 다솜이의 득표수가 나머지 모든 후보의 득표수를 초과하면 종료합니다.
• 매수 횟수를 출력합니다.

Step4. 코드 구현

import sys
from heapq import heappop, heappush, heapify
N = int(sys.stdin.readline().strip())
votes = [int(sys.stdin.readline().strip()) for _ in range(N)]
def sol(N, votes):
    dasom = votes[0]
    others = [-v for v in votes[1:]]
    heapify(others)
    cnt = 0
    
    while others and dasom <= others[0]:
        max_votes = -heappop(others)
        dasom += 1
        max_votes -= 1
        cnt += 1
        
        heappush(others, -max_votes)
    return cnt
print(sol(N=N, votes=votes))  

• 코드 설명:
  • heapq를 이용한 최대 힙:
    • Python의 heapq는 기본적으로 최소 힙을 제공하므로, 음수 값을 활용하여 최대 힙처럼 사용합니다.
    • 득표수가 가장 많은 후보를 매수하는 작업이 빠르게 수행됩니다.
  • 다솜이의 득표수 관리:
    • dasom 을 업데이트하며, 매수 과정마다 다솜이의 득표수를 증가시킵니다.
  • 매수 횟수 증가:
    • 후보의 득표수를 감소시키고 매수 횟수를 증가시킨 뒤, 해당 후보를 다시 힙에 삽입합니다.
  • 종료 조건:
    • 다솜이의 득표수가 나머지 모든 후보의 득표수보다 많아지면 반복을 종료합니다.
• 시간 복잡도:
  1. 힙 작업:
     • 힙에서 가장 큰 값을 꺼내거나 삽입하는 작업은 $O(\log N)$입니다.
     • 최대 M번의 매수를 수행하므로, 힙 작업의 전체 시간 복잡도는 $O(M \log N)$입니다.
  2. 최악의 경우:
     • 모든 표를 매수해야 한다면 M=총 득표수의 합.
     • 득표수의 합은 N×100 이하이므로, 복잡도는 $O((N \times 100) \log N).$
• 결론
  

---

4. 마무리

이번 문제는 다솜이가 국회의원 선거에서 최소한의 매수로 승리하기 위한 전략을 설계하는 문제였습니다. 문제 해결의 핵심은 그리디 알고리즘과 최대 힙을 사용하여 득표수가 가장 많은 후보를 우선적으로 매수하는 방식이었습니다. 이를 통해 다솜이의 득표수를 효율적으로 증가시키고 매수 횟수를 최소화할 수 있었습니다. Python의 heapq 모듈을 활용하여 힙 연산을 빠르게 처리하며, 문제를 $O(M \log N)$의 시간 복잡도로 해결했습니다. 이번 문제를 통해 힙 자료구조와 그리디 접근법의 유용성을 다시 한번 체감할 수 있었습니다.

읽어주셔서 감사합니다.