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

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

1417번: 국회의원 선거

---

Level: Silver V

Solved By: Priority Queue, Greedy

 

아마 우선순위 큐라는 키워드가 없었다면 문제를 푸는데 어려움을 겪었을 것 같습니다.

 

1번의 value를 따로 받고 최댓값 우선순위 큐를 선언하여 나머지 value들을 넣어줍니다. 그러면 최댓값을 순서로 우선순위 큐에 담겨 있습니다.

 

1번의 value와 우선순위 큐의 top과 비교를 하며 크거나 같다면 표 하나를 뺏어야 합니다.

즉, 표를 가져왔으니 value에는 1을 더해주고, top에는 1을 빼주어 다시 우선순위 큐에 push 합니다. 이러한 과정을 1번의 value가 우선순위 큐의 top보다 작은 동안 반복하는 코드를 짭니다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int N;

struct cmp{
    bool operator()(int a,int b){
        return a < b;
    }
};

priority_queue<int, vector<int>, cmp> pq;

int main(){
    cin >> N;
    int v; cin >> v;
    for(int i = 0; i < N - 1; i++){
        int a; cin >> a;
        pq.push(a);
    }
    
    int res = 0;
    while(!pq.empty() && v <= pq.top()){
        int t = pq.top();
        pq.pop();
        pq.push(t - 1);
        res++;
        v++;
    }
    
    cout << res;
    return 0;
}