1417번 : 국회의원 선거 [C++]

문제 링크

성공 여부(걸린 시간): 성공 (5분)

아이디어

다솜이를 제외한 후보들의 지지자 수에 대해서 우선순위큐에 저장을 해준다.

그리고나서 다솜이보다 다른 후보들이 지지자들이 다솜이의 지지자의 수보다 적을때까지 한명씩 매수를 진행한다.

 

만약 우선순위큐의 top값이 다솜의 지지자의 수보다 작아지는 순간
반복을 종료하고 매수한 인원수를 출력해준다.

풀이 코드

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    priority_queue<int> pq;
    int N;
    cin >> N;
    int dasom;
    cin >> dasom;
    for (int i = 1; i < N; i++) {
        int num;
        cin >> num;
        pq.push(num);
    }
    int answer = 0;
    while (!pq.empty() && pq.top()>=dasom) {
        int newTop = pq.top()-1;
        pq.pop();
        pq.push(newTop);
        answer++;
        dasom++;
    }
    cout << answer;
    return 0;
}