[C++] 백준 1417번 국회의원 선거

1. 문제이해

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

1417번: 국회의원 선거

 

다솜이를 포함한 국회의원 후보들이 몇명인지를 입력받고, 각 후보들의 득표수를 입력받는다.

만약 다솜이의 득표수가 다른 국회의원 후보들의 득표수보다 적다면,

다른 국회의원 선수들의 표를 매수하려고 한다.

가장 많은 득표수를 받은 사람이 국회의원으로 당선된다고 할때,

다솜이가 최소 몇표를 매수해야 되는지를 출력하는 알고리즘을 구현하는 것이 목표이다.

 

 

 

2. 문제풀이

 

구현하는데 정말 오래걸렸다..

원리는 간단하다.

다솜이보다 표수가 많은 후보들의 표를 다솜이의 표가 가장 많아질때까지 매수해 국회의원으로 당선시키면 된다.

여기서 중요한 점은, 매수해야하는 최소득표수는

다솜이를 제외한 다른 후보들의 득표수 중 최대득표수에서 매수해주어야 한다는 것이다.

 

한가지 예를 들어보자.

만약 다솜이의 득표수가 6, 다른 후보자들의 득표수가 8 2 9 10 3 라고 하자.

여기서 최대득표수를 골라내 보면 10이고, 다솜이의 득표수보다 많으므로, 매수한다.

따라서 다솜이의 득표수는 7, 다른 후보자들의 득표수는 8 2 9 9 3 이 된다.

이를 반복하면,

8, 8 2 8 9 3

9, 8 2 8 8 3

이 되어, 다솜이가 9 표가 되면, 즉, 4표를 매수하면 국회의원으로 당선이 된다.

 

만약, 최대득표수에서 매수를 하지 않고, 그저 다솜이보다 표수가 많은 후보자들에게서 매수를 한다고 해보자.

6, 8 2 9 10 3 에서, 첫번째 후보가 8, 다솜이보다 많으므로 매수한다.

7, 7 2 9 10 3 이 되고, 첫번째 후보와 다솜이의 득표수가 같으므로 매수한다.

8, 6 2 9 10 3이 되고, 세번째 후보가 득표수가 더 많으므로, 매수한다.

9, 6 2 8 10 3이 되고, 네번째 후보가 득표수가 더 많으므로, 매수한다.

10, 6 2 8 9 3이 되고, 5표를 매수하면 다솜이가 당선이 된다.

 

처음 구현을 할때, 두번째 방법으로 구현을 해, 제대로 된 결과가 나오지 않는 문제가 발생했었다.

(위와같은 반례를 찾는데 상당한 시간이 걸렸다..)

위와 같이, 다솜이가 국회의원에 당선되기 위해 매수해야하는 최솟값을 구하기 위해서는,

반드시 해당 국회의원들의 득표수중 최댓값에서 매수해주어야한다.

 

 

 

3. 소스코드

#include <iostream>
#include <algorithm>
using namespace std;

int vote[1000];

int main() {
	int count = 0;
	int candidate;
	int dasom;

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> candidate;
	cin >> dasom;

	for (int i = 0; i < candidate - 1; i++) {
		cin >> vote[i];
	}

	while (true) {
		int find_max = 0;
		int index = 0;

		// 가장 큰 값 찾기
		for (int i = 0; i < candidate - 1; i++) {
			if (find_max < vote[i]) {
				find_max = vote[i];
				index = i;
			}
		}
		// 찾은 값이 다솜이의 표수보다 적다면 출력
		if (dasom > find_max) {
			cout << count << "\n";
			break;
		 }
		// 찾은 값이 다솜이의 표수보다 많다면 뺏어옴
		dasom++;
		vote[index]--;
		count++;
	}

}

원래는 정렬함수를 이용해서 정렬후 최댓값을 비교하는 방식으로 구현했지만,

해당 방법은 계속해서 시간초과가 발생했다.

while문 안에서 계속해서 정렬을 하게 되어 많은 시간이 소요되는것이 문제였던것 같다.

따라서 정렬함수 대신, 최댓값을 찾는 알고리즘을 통해 코드를 위와 같이 구현했다.

 

우선, 후보자의 수(candidate), 다솜이의 표수(dasom), 나머지 후보들의 표수(vote[i])를 입력받는다.

이어지는 while문 안의 for문을 통해 다솜이를 제외한 다른 후보들의 득표수중 가장 많은 득표수를 찾고,

해당 특표수가 다솜이의 득표수보다 많으면, 매수한다.

(dasom++, vote[index]--, count++ / 각각 다솜이의 득표수+1, 해당 후보의 득표수-1, 매수한 표수+1)

만약 다른 후보들의 득표수중 가장 많은 득표수가 다솜이의 득표수보다 작게 되면,

다솜이의 득표수가 가장 많은 것이므로, 이때까지 매수한 표수(count)를 출력하고 while문을 빠져나간다.

 

 

---

구현하기 너무 힘들었다..

첫번째 썼던 방법은 반례를 찾기가 힘들었고, 두번째 방법은 시간초과가 뜨니..

코드를 정말 며칠을 수정한것같다..😭