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

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 우선순위 큐를 활용해 풀이했다.

1) 다솜이를 제외한 각 후보의 투표수와 인덱스를 저장하는 pair들을 저장하는 우선순위 큐, 다솜이를 포함한 후보들의 투표수를 저장하는 벡터 를 선언한다. 우선순위 큐는 투표수의 내림차순으로 정렬된다.
2) 후보가 1명일 때(== 다솜이 뿐일 때)는 바로 0을 출력한다.
3) 후보가 여러 명이면 일단 투표수를 저장하는 벡터에 각 기호의 투표수를 차례대로 저장한다.
4) 반복문으로 다솜이와 나머지 후보들의 투표수를 차례대로 비교한다.

• 먼저 투표수를 저장하는 벡터를 전부 돌면서 다솜이의 투표수와 비교한다.
  • 다솜이의 투표수가 현재 순서 후보의 투표수보다 적거나 같으면 우선순위 큐 맨 앞에 있는 가장 투표수가 큰 후보의 투표수를 1 깎고, 다솜이의 투표수를 1 증가시킨다 (벡터에서). 또한 매수한 사람의 수를 저장하는 count도 1 증가시킨다.
  • 위 과정을 계속해서 반복한 결과, 모든 후보의 투표수가 다솜이보다 적으면 그 때 count를 출력한다.

🖥️ 풀이 코드

#include <iostream>
#include <algorithm>
#include <tuple>
#include <string>
#include <queue>

using namespace std;
typedef pair<int, int> pii; // 사람 수, 인덱스

// 사람 수의 내림차순으로 정렬하는 비교연산자 구현
struct Compare
{
	bool operator()(pii a, pii b)
	{
		return a.first < b.first;
	}
};

int main(int argc, char** argv)
{
	priority_queue<pii, vector<pii>, Compare> pq;	// 우선순위 큐 선언 (사람 수의 내림차순으로 우선순위 큼) 
	vector<int> pVec;	// 기호 별 사람 수 저장 
	int n = 0, dasom = 0, count = 0;
	cin >> n;
	cin >> dasom;
	pVec.push_back(dasom);

	if (n == 1)
	{
		cout << 0;
		return 0;
	}
		
	for (int i = 1; i < n; i++)
	{
		int pNum;	// 사람 수
		cin >> pNum;
		pVec.push_back(pNum);
		pq.push(pii(pNum, i));
	}

	while (true)
	{
		for (int i = 1; i < pVec.size(); i++)
		{
			if (pVec[0] <= pVec[i])
				break;
			
			if (i == pVec.size() - 1)
			{
				cout << count;
				return 0;
			}		
		}

		int topNum = pq.top().first;
		int index = pq.top().second;
		pq.pop();
		pq.push(pii(topNum - 1, index));
		pVec[0] += 1;
		pVec[index] = topNum - 1;
		count++;
	}
}