백준 1417 국회의원 선거 (c++) : 피너클

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

1417번: 국회의원 선거

그리드 문제다.

국회의원이 되기 위해서는 다른 후보들보다 표를 더 많이 받아야한다.

그러니 다른 후보중 가장 많은 표를 받을 후보보다 많은 표를 받으면 뒨다.

cin >> n;
cin >> m;
for (int i = 0; i < n - 1; i++) {
	int a;
	cin >> a;
	pq.push(a);
}

값들을 입력받는다. 이때 기호 1번의 표수는 m에 입력받고 나머지 후보의 표수는 pq에 입력받는다.

pq의 top에는 후보들중 가장 많은 표수를 받는 사람의 표수가 나온다.

int ans = 0;
while (!pq.empty()) {
	int top = pq.top();
	pq.pop();
	if (top < m) break;
	else {
		pq.push(top - 1);
		m++;
		ans++;
	}
}

ans는 매수는 사람의 수다.

반복문은 pq가 비어있지 않은 동안 실행된다.

int top에 pq의 top을 할당하고 pq.pop을 한다. top에는 다른 후보가 받는 가장 많은 표수가 입력된다.

만약 내가 받는 표수가 top보다 크다면 내가 1등이니 바로 반복문을 빠져나온다.

아니면 top에서 표를 하나 뺏어온다.

pq에 top-1을 집어넣고 (표를 뺏은 후보의 표수를 다시 pq에 집어넣는다)

m++를 해주고 (한표 뻇었으니 한표 추가해준다)

ans++해준다. (한번 표를 뺏었으니 추가해준다.)

이를 반복하면 답이 나온다.

cout << ans << endl;

마지막으로 답을 출력하면 된다.

#include <iostream>
#include <queue>

using namespace std;

int n, m;
priority_queue<int> pq;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n;
	cin >> m;
	for (int i = 0; i < n - 1; i++) {
		int a;
		cin >> a;
		pq.push(a);
	}
	int ans = 0;
	while (!pq.empty()) {
		int top = pq.top();
		pq.pop();
		if (top < m) break;
		else {
			pq.push(top - 1);
			m++;
			ans++;
		}
	}
	cout << ans << endl;
}

전체코드다.