본문 바로가기
c언어/baekjoon.c

[1417] 국회의원 선거 (자료구조, 우선순위 큐)

by 로토마 2022. 9. 18.

국회의원 선거 백준 1417번

문제

다솜이는 사람의 마음을 읽을 수 있는 기계를 가지고 있다. 다솜이는 이 기계를 이용해서 2008년 4월 9일 국회의원 선거를 조작하려고 한다.

다솜이의 기계는 각 사람들이 누구를 찍을 지 미리 읽을 수 있다. 어떤 사람이 누구를 찍을 지 정했으면, 반드시 선거때 그 사람을 찍는다.

현재 형택구에 나온 국회의원 후보는 N명이다. 다솜이는 이 기계를 이용해서 그 마을의 주민 M명의 마음을 모두 읽었다.

다솜이는 기호 1번이다. 다솜이는 사람들의 마음을 읽어서 자신을 찍지 않으려는 사람을 돈으로 매수해서 국회의원에 당선이 되게 하려고 한다. 다른 모든 사람의 득표수 보다 많은 득표수를 가질 때, 그 사람이 국회의원에 당선된다.

예를 들어서, 마음을 읽은 결과 기호 1번이 5표, 기호 2번이 7표, 기호 3번이 7표 라고 한다면, 다솜이는 2번 후보를 찍으려고 하던 사람 1명과, 3번 후보를 찍으려고 하던 사람 1명을 돈으로 매수하면, 국회의원에 당선이 된다.

돈으로 매수한 사람은 반드시 다솜이를 찍는다고 가정한다.

다솜이가 매수해야하는 사람의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 후보의 수 N이 주어진다. 둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 이렇게 총 N개의 줄에 걸쳐 입력이 들어온다. N은 50보다 작거나 같은 자연수이고, 득표수는 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 다솜이가 매수해야 하는 사람의 최솟값을 출력한다.

예제 입력 1 복사

3
5
7
7

예제 출력 1 복사

 

2

예제 입력 2 복사

4
10
10
10
10

예제 출력 2 복사

1

예제 입력 3 복사

1
1

예제 출력 3 복사

0

예제 입력 4 복사

5
5
10
7
3
8

예제 출력 4 복사

4

 

풀이과정 및 코드

전체 로직 구현 구상도 (수작업 ㅎ)

✨나만의 Point

- 특별한 계산이 필요한 모든 로직을 함수 단위로 묶어, 로직을 직관적으로 볼 수 있게끔 구성했다.

- 전역변수를 활용해, 함수간 인자를 주고 받을 필요가 없어 코드를 간결하게 구성했다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
 
int N, DasomN,buyN=0//Number of Candidate, Number of votes who voted Dasom, Number of people to buy
int * vote_cnt; //Pointer variable to save the total number of Votes
 
void insertVoteN(); //Function to insert&save the total number of Voted for each Candidate
void selectSort(); //Fuction to Descending through selectionSort
void buyVoteN(); //Function to estimate the Number of people to buy
 
int main()
{    
    insertVoteN();    // Call the Function to insert&save the Number of Voted for each Candidate
    buyVoteN(); // Call the Fucntion to Estimate the Number of people to buy
 
    printf("%d", buyN);  //Print the result of people to buy
 
    free(vote_cnt); //free the vote_cnt array
    return 0//Quit program 
}
// Function to insert&save the total number of Voted for each Candidate
void insertVoteN() {
    scanf("%d"&N); //insert the Number of Candidate
    vote_cnt = (int*)malloc(sizeof(int)*N);// dynamically allocate to save the votes for each candiate
    for (int i = 0; i < N; i++) { 
        scanf("%d"&vote_cnt[i]); //insert the number of votes for each candidate
    }
    DasomN = vote_cnt[0]; //save the Number of votes of Dasom
}
 
//Fuction to Descending through selectionSort
void selectSort() { 
    int max_idx, tmp; //variable for save max array index, empty variable for swap
    //SelectSort algorithms
    for (int i = 1; i < N; i++) { //except the Dasom's value 
        max_idx = i; //initialize max index value 
        for (int j = i + 1; j < N; j++) { // find the max array index 
            if (vote_cnt[max_idx] < vote_cnt[j]) { // if max array found?
                max_idx = j; //update the value
            }
        }
        //swap for Descending
        tmp = vote_cnt[i]; 
        vote_cnt[i] = vote_cnt[max_idx];
        vote_cnt[max_idx] = tmp;
    }
}
 
//Function to estimate the Number of people to buy
void buyVoteN() {
    selectSort(); //Organize the array to Decsending
    while (DasomN <= vote_cnt[1]) { //if the Number of VotesN of other Candidate's is bigger than Dasom's?
        DasomN++//buy one votes to Dasom
        vote_cnt[1--//discount one votes from other Candidate's
        buyN++// added the number of buying 
        selectSort(); //Organize the array to Decsending again to estimate the biggest value is still much than Dasom's
        //printf("many many %d \n", vote_cnt[i]); for debugging
    }
}
cs

 

⚠️이때 주의!!! )

재정렬 하지 않고, 배열값만을 순차적으로 비교하면서 BuyN 값을 계산할 경우.

가장 최적의 최소 BuyN값을 구하지 못하는 경우가 발생한다.

 

EX) 다솜:1, 다른 후보자들: 15, 14 인 경우

예외 발생