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

문제

풀이

기본 아이디어는 다솜(기호1번)의 득표수보다 다른 후보의 득표수가 크거나 같으면 매수해서 다솜의 득표수는 +1 하고 표를 뺏긴 후보의 득표수는 -1을 하는 것입니다.

문제에서 매수해야하는 사람의 최솟값을 구하라고 했습니다.
따라서 최대 득표수를 가진 후보의 득표를 뺏어오는 것이 매수하는 사람을 최소로 만들수 있습니다.

코드

#include <cstdio>
using namespace std;

int main() {
    int N;
    scanf("%d", &N);
    int *voteArr = new int[N];

    for(int i = 0; i < N; i++) {
        int vote;
        scanf("%d", &vote);
        voteArr[i] = vote;
    }

    int count = 0;

    while(1) {
        int maxIndex = 0;
        int max = 0;
        
        for(int i = 0; i < N; i++) {
            if(max <= voteArr[i]) {
                max = voteArr[i];
                maxIndex = i;
            }
        }

        if(maxIndex != 0) {
            count++;
            voteArr[0]++;
            voteArr[maxIndex]--;
        }
        else {
            break;
        }
    }
    printf("%d\n", count);
    return 0;
}

수정한 풀이

위 풀이에서 맞았지만 시간복잡도를 더 줄일 수 있을 것 같습니다.
위 코드에서 최대 득표수를 찾는 과정을 for문으로 구현해서 O(N) time complexity를 가집니다.
Heap을 이용한 우선순위 큐를 사용해서 최대 득표수를 찾으면 O(log N) time complexity를 가집니다. (C++ STL 사용예정)

수정한 코드

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

int main() {
    int N;
    scanf("%d", &N);

    int dasom;
    scanf("%d", &dasom);

    priority_queue<int> pq;
    for(int i = 0; i < N-1; i++) {
        int vote;
        scanf("%d", &vote);
        pq.push(vote);
    }

    int count = 0;
    while(N != 1) {
        if(dasom <= pq.top()) {
            int max = pq.top();
            pq.pop();
            max--;
            dasom++;
            pq.push(max);

            count++;
        }
        else {
            break;
        }
    }
    printf("%d\n", count);
    return 0;
}