99클럽 코테 스터디_4기 23일차 TIL

TODAY TIL

다솜이는 사람의 마음을 읽는 기계를 이용해 국회의원 선거에서 자신을 찍지 않을 사람들을 매수하려고 합니다. 목표는 다른 후보들의 득표수를 초과하는 것입니다. 이 글에서는 다솜이가 최소 몇 명을 매수해야 당선될 수 있는지를 계산하는 방법을 설명합니다.

 

문제 설명

1. 입력 조건:
   • 후보 수 NNN이 주어집니다.
   • 각 후보의 득표수가 순서대로 입력됩니다.
   • 기호 1번 후보가 다솜이입니다.
2. 출력 조건:
   • 다솜이가 매수해야 하는 사람의 최소 수를 출력합니다.
3. 제약 조건:
   • 후보 수 NNN: 최대 50
   • 각 후보의 득표수: 최대 100
4. 예제 입력/출력

입력:

3
5
7
7

 

출력:

2

 

해결 방법

문제를 해결하기 위해 다음과 같은 단계로 접근합니다:

1. 입력 데이터를 읽기:
   • 후보 수와 각 후보의 득표수를 리스트로 저장합니다.
   • 다솜이의 득표수는 따로 저장하고, 나머지 후보들의 득표수를 관리합니다.
2. 매수 작업 반복:
   • 다른 후보들의 득표수를 내림차순으로 정렬합니다.
   • 가장 많은 득표수를 가진 후보를 매수하여 다솜이의 득표수를 증가시킵니다.
   • 다솜이의 득표수가 다른 모든 후보보다 많아질 때까지 이 작업을 반복합니다.
3. 매수 횟수 계산:
   • 매수 횟수를 카운트하면서, 다솜이의 득표수가 다른 후보들보다 많아질 때 결과를 출력합니다.

Python 코드

# 입력받기
N = int(input())  # 후보 수
votes = [int(input()) for _ in range(N)]  # 각 후보의 득표수

# 초기 설정
dasom_votes = votes[0]  # 다솜이의 득표수
other_votes = votes[1:]  # 다른 후보들의 득표수
bribes = 0  # 매수한 사람 수

# 매수 작업
while other_votes and max(other_votes) >= dasom_votes:
    # 가장 많은 득표수를 가진 후보의 표를 매수
    max_index = other_votes.index(max(other_votes))  # 최대값의 인덱스 찾기
    other_votes[max_index] -= 1  # 표 매수 (1 감소)
    dasom_votes += 1  # 다솜이의 표 증가
    bribes += 1  # 매수 횟수 증가

# 결과 출력
print(bribes)

 

코드 설명

1. 입력 처리:
   • 후보 수 NNN과 각 후보의 득표수를 입력받아 리스트로 저장합니다.
   • 다솜이의 득표수는 dasom_votes에, 나머지 후보들의 득표수는 other_votes 리스트로 관리합니다.
2. 매수 작업:
   • while 루프를 통해 다솜이의 득표수가 다른 후보들의 최대 득표수를 초과할 때까지 반복합니다.
   • 가장 많은 득표수를 가진 후보의 표를 하나 매수하고, 다솜이의 득표수를 증가시킵니다.
3. 결과 출력:
   • 매수 횟수는 bribes 변수에 저장되며, 반복이 끝나면 최솟값이 출력됩니다.

예제 실행

입력

3
5
7
7

 

출력

2

 

추가 설명

이 코드의 핵심은 다솜이의 득표수가 다른 후보들보다 많아질 때까지 반복적으로 매수하는 것입니다. 가장 득표수가 많은 후보를 우선 매수하는 전략을 사용하여 최솟값을 계산합니다.

---

최적화 고려사항

• 후보 수 NNN이 최대 50이므로, 매수 작업의 복잡도는 적절한 수준입니다.
• max\text{max}max 연산을 사용하는 만큼, 리스트 길이에 따라 작업 시간이 영향을 받을 수 있습니다.

---

마무리

이 문제는 그리디 알고리즘을 활용하여 반복적으로 최대값을 줄이는 전략을 사용합니다. 매수 전략을 효율적으로 구현하여 다솜이가 국회의원에 당선되도록 만드는 과정을 함께 배웠습니다.

코드와 예제 실행 결과를 참고하여 자신만의 해결 방법을 구현해 보세요! 😊