[백준 1417] 국회위원 선거

문제 풀이

 

입력 범위가 최대 1000이라 다양한 방법이 있을 수 있다.

 

다솜이가 국회위원으로 뽑히려면 최소한 모든 투표보다는 +1 커야 한다.

3 3 3 3 3 이라면 다솜이는 최소한으로 1명을 꼬셔야 한다는 것이다.

 

3 3 4 7 5 3 이라면?

제일 많은 득표수를 가진 7에게서 3번 뺏으면? 다솜이가 당선된다.

하지만 다른 방법으로도 당선될 수도 있다.

 

어떻게 하면 최소한으로 뽑을 수 있을까?

제일 많은 득표수를 가진 사람부터 빼앗으면 된다.

 

[3 3 4 7 5 3] 를 통해서 확인해보자.

 

다솜이가 3개의 득표 수고, 나머지 국회위원들 3 4 7 5 3 중에서 가장 많은 득표수를 가진 사람은 7표이므로

7 -> 6표로 깎아주고, 다솜이는 3 -> 4표로 증가시켜준다.

 

다솜이가 4개의 득표수고, 나머지 국회위원들 3 4 6 5 3 중에서 가장 많은 득표수를 가진 사람은 6표이므로

6 -> 5표로 깎아주고, 다솜이는 4 -> 5표로 증가시켜준다.

 

다솜이가 5개의 득표수고, 나머지 국회위원들 3 4 5 5 3 중에서 가장 많은 득표수를 가진 사람은 5표이므로

5 -> 6표로 깎아주고, 다솜이는 5 -> 6표로 증가시켜준다.

 

이렇게 하면 3개의 표만 뺏어오면 다솜이가 당선되게 된다.

 

가장 많은 득표수를 빠르게 구할 수 있는 연산은 다양하지만, 우선순위 큐(최대 힙) 구조를 이용하면 쉽게 해결할 수 있다.

 

소스 코드

 

#include <iostream>
#include <queue>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n, dasom;
	cin >> n;
	priority_queue<int> pq;
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		if (i == 0)
			dasom = x;
		else
			pq.push(x);
	}

	int ans = 0;
	while (!pq.empty())
	{
		int now = pq.top();
		pq.pop();

		if (dasom <= now)
		{
			dasom++;
			now--;
			ans++;
			pq.push(now);
		}
		else
			break;
	}

	cout << ans << endl;
	return 0;
}