(백준 제1417호) 국회의원선거

문제

다솜이는 마음을 읽을 수 있는 기계를 가지고 있습니다.

다솜이는 이 기계를 이용해 2008년 4월 9일 국회의원 선거를 조작한다.

다솜이의 기계는 각 사람이 누구에게 총을 쏠지 미리 읽을 수 있습니다.

어떤 사람이 누구에게 투표할지 결정할 때, 그는 선거에서 그 사람에게 투표해야 합니다.

현재 형택구 N에는 국회의원 후보가 있다.

다솜이는 이 기계로 M 마을 사람들의 마음을 읽는다.

다솜이는 1번이다.

다솜이는 마음을 읽고 자신에게 투표하기 싫은 사람들에게 돈을 주고 자신이 국회의원이 될 수 있도록 뇌물을 주려고 한다.

남의 목소리보다 많은 그가 득표수를 가지면 그 사람이 국회의원으로 선출됩니다.

예를 들어 마음읽기 결과 2번에 투표하고 싶은 1명과 1번 심볼이 5표, 2번 심볼이 7표, 3번 심볼이 7표라면 다솜이가 동의하고 3번에 투표합니다.

돈으로 사람 사면 국회의원 당선된다.

돈 주고 산 사람이 다솜이 사진을 찍어야 하는 것으로 이해된다.

다솜이를 사야 하는 사람의 최저 가격을 출력하는 프로그램을 작성하세요.

기입

후보의 수 N은 첫 번째 라인에 주어진다.

두 번째 행부터 심볼 1번을 가져가려는 사람의 수, 심볼 2번을 가져가려는 사람의 수 등 총 N개의 행에 대한 입력을 받는다.

N은 50 이하의 자연수이고 득표수는 100 이하의 자연수이다.

누르다

첫 번째 라인은 다솜이가 구매해야 하는 최소 인원수를 출력합니다.

예

개념 핵심/솔루션 포인트 요약

1. 다솜이 후보가 아닌 후보의 우선순위 득표수 입력

2. 우선순위 큐에는 임시로 가장 높은 값을 저장하고, 다솜이의 득표수와 비교하여 빼서 다시 큐에 넣는다.

3. 후보가 1인일 경우 예외처리(다솜이만 해당)

설명

#include <iostream>
#include <queue>

using namespace std;
int n, m, temp, d, cnt = 0;
priority_queue<int> arr;

void elect() {
	if (d > arr.top())	return;
	else {
		temp = arr.top();
		arr.pop();
		temp--;
		arr.push(temp);
		d++;
		cnt++;
		elect();
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	cin >> d;
	if (n == 1) {
		cout << cnt;
		return 0;
	}
	for (int i = 0; i < n-1; i++) {
		cin >> m;
		arr.push(m);
	}
	elect();
	cout << cnt;
	return 0;
}