기본 아이디어는 다솜(기호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;
}