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

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

풀이

다솜이의 현재 득표수와 다른 후보의 득표수 중 최대값을 계속 비교해서
다솜이의 득표수가 더 작으면 매수할 사람을 증가시킨다.

다솜이 외 후보의 득표수를 최대 힙으로 관리하여, top 요소를 다솜이와 비교하는 것이다.

코드

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

int main()
{
    int n, dasom, ans = 0;
    priority_queue<int> pq;
    
    cin >> n >> dasom;
    
    while(--n){
        int x;
        cin >> x;
        pq.push(x);
    }

    while(!pq.empty() && dasom <= pq.top()){
        int max = pq.top();
        pq.pop();
        pq.push(max-1);
        dasom++;
        ans++;
    }
    
    cout << ans;
    
    return 0;
}

오답 이유

처음 제출한 코드에서 segmentation fault가 발생했는데, 이는 잘못된 메모리 참조 때문이라고 한다.

코드를 살펴보니, 우선순위 큐가 비어있을 때를 처리해주지 않아서 생긴 문제였다.

• 첫번째 코드 (오답)

while(dasom <= pq.top()){ ... }

• 두번째 코드 (정답)

while(!pq.empty() && dasom <= pq.top()){ ... }

추가로, !pq.empty()를 조건문 가장 앞에 써야 한다는 점을 기억하자.

while(dasom <= pq.top() && !pq.empty()){ ... }

이 경우 pq.top()을 먼저 실행하기 때문에 똑같이 segmentation fault가 발생한다.