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

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

1417번: 국회의원 선거

풀이 :

- 다솜이보다 큰 후보의 표를 하나씩 가져와서 다솜이의 표에 더해서 다솜이의 표가 최댓값이 되어야 한다.

- 이렇게 다솜이의 표를 최댓값으로 만들기 위한 최솟값을 구해야 한다. 

- 같은 표를 가진 후보가 여러명 있을 수도 있고, 최댓값이 여러개일 경우, 한 후보의 표만 빼서는 최솟값을 구할 수 없다.

- n이 100밖에 안되기 때문에 배열의 인덱스를 표 값으로 생각하고, 배열을 계속 탐색하며 매번 배열의 최댓값을 구했다.

- 다솜이의 표보다 큰 최댓값이 나오지 않을 때까지 최댓값을 구하고, 구한 최댓값과 다솜이의 표를 조절하여 정답을 구할 수 있었다.

 

코드 :

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

int main(){
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    int n, num, cnt, arr[105] = {0, }, flag, max_index;
    
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> num;
        if(i == 0){
            flag = num; //다솜이의 표는 배열에 넣지 않고 따로 저장
        }else{
            arr[num]++; //각 인덱스는 표. 즉, 표의 갯수 저장
        }
    }
    cnt = 0;
    while(1){ //일단 무한 루프
        max_index = 0; //최대값을 찾기 위해 루프 돌 때마다 초기화
        for(int i=1; i<101; i++){ //배열 전체 탐색
            if(arr[i] > 0 && i >= flag){ //다솜이보다 큰 표 수 중 최댓값의 인덱스를 구한다
                max_index = i;
            }
        } 
        if(max_index > 0){ //최댓값이 존재한다면, 다솜이가 표를 하나 매수하기 때문에,
            arr[max_index]--; //최댓값의 인덱스의 수는 하나 빼고,
            arr[max_index-1]++; //최댓값인덱스의 이전 인덱스에 하나 더해준다
            flag++; //다솜이의 표를 하나 올려주고,
            cnt++; //카운트도 올려준다
        }else{ //최댓값이 존재하지 않는다면, 이미 다솜이가 최댓값이므로 break;
            break;
        }
    }
    cout << cnt << '\n';
}