(C++) - 백준(BOJ) 1417 : 국회의원 선거

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

1417번: 국회의원 선거

우선순위 큐를 이용하는 자료구조 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

총 후보 수 n, 다솜을 찍은 사람 수 dasom, 정답을 출력할 변수 ans, 우선순위 큐 pq를 선언 후 적절히 입력받습니다.

📔 풀이과정

우선순위 큐의 default는 max heap입니다. 즉, top에는 항상 최댓값을 가지고 있습니다.

pq에 원소가 존재하며 항상 top만 비교하며 dasom값 이상인 동안 while loop를 수행합니다.

매번 top으로부터 1표씩 dasom에게 추가하며 갱신된 top값을 다시 pq에 push해줌으로써 dasom이 가져갈 최소 표 수를 구할 수 있습니다.

📔 정답출력

ans를 출력해줍니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
int n, dasom, ans;
priority_queue <int> pq;

int main(){
    cin >> n >> dasom;
    for(int i = 1, x; i < n; i++) {
        cin >> x;
        pq.push(x);
    }

    while(pq.size() && pq.top() >= dasom){
        int x = pq.top();
        pq.pop();
        ans++, dasom++;
        pq.push(x-1);
    }

    cout << ans;
}