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

문제링크

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

1417번: 국회의원 선거

 

문제

다솜이는 사람의 마음을 읽을 수 있는 기계를 가지고 있다. 다솜이는 이 기계를 이용해서 2008년 4월 9일 국회의원 선거를 조작하려고 한다.
다솜이의 기계는 각 사람들이 누구를 찍을 지 미리 읽을 수 있다. 어떤 사람이 누구를 찍을 지 정했으면, 반드시 선거때 그 사람을 찍는다.
현재 형택구에 나온 국회의원 후보는 N명이다. 다솜이는 이 기계를 이용해서 그 마을의 주민 M명의 마음을 모두 읽었다.
다솜이는 기호 1번이다. 다솜이는 사람들의 마음을 읽어서 자신을 찍지 않으려는 사람을 돈으로 매수해서 국회의원에 당선이 되게 하려고 한다. 다른 모든 사람의 득표수 보다 많은 득표수를 가질 때, 그 사람이 국회의원에 당선된다.
예를 들어서, 마음을 읽은 결과 기호 1번이 5표, 기호 2번이 7표, 기호 3번이 7표 라고 한다면, 다솜이는 2번 후보를 찍으려고 하던 사람 1명과, 3번 후보를 찍으려고 하던 사람 1명을 돈으로 매수하면, 국회의원에 당선이 된다.
돈으로 매수한 사람은 반드시 다솜이를 찍는다고 가정한다.
다솜이가 매수해야하는 사람의 최솟값을 출력하는 프로그램을 작성하시오.

조건

시간제한 : 2초
메모리 제한 : 128 MB

입력

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

출력

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

 

문제정리

1. 다솜이는 기호 1번
2. 다솜이가 다른 사람을 매수해서 그 사람의 표를 뺃음
3. 다른 모든 사람의 득표수 보다 다솜이의 득표수가 많아지면 당선
4. 다솜이를 당선시키기 위해 매수해야될 최솟값

이 문제의 경우 다솜이를 당선시키기 위해서 사람을 매수 하여야 하는데 매수하는 사람의 최솟값을 구하는 문제입니다.

다솜이를 빠르게 당선시키면서 최솟값을 구하려면 다솜이를 제외한 투표수가 제일 높은 사람의 매수를 뺃으면 될 것입니다.

 

다솜이를 제외한 후보들을 오름차순으로 정렬하여 제일 큰값을 찾고 그 값과 다솜이랑 비교하여 다솜이가 작다면 값을 뺃고 크다면 카운팅 된 갯수를 출력하면 되는 문제입니다.

 

여기서 주의할점은 후보의 가장 큰 값을 찾는 것입니다. 그렇기 때문에 매번 반복할 때마다 정렬을하여 최고값을 찾고 있습니다.  ( 득표수가 적다고 판단하여 Sort를 하였습니다 아니면 다른방법을 더 연구해봐야 할 것 같습니다.)

 

그리고 알고리즘 분류에 우선순위 큐가 있는데 이점도 더 찾아봐야할 것 같습니다.

C# 코드

static void Main(string[] args)
{
    StreamWriter writer = new StreamWriter(OpenStandardOutput());
    StreamReader reader = new StreamReader(OpenStandardInput());
 
    int N = int.Parse(reader.ReadLine());
    int Dasom = int.Parse(reader.ReadLine());
    int count = 0;
 
    if (N == 1) // 후보가 한명이라면 0 출력
    {
        writer.WriteLine(0);
    }
    else
    {
        int[] person = new int[N - 1];
 
        // 다솜이를 제외한 나머지 당선인 입력
        for (int i = 0; i < N - 1; i++)
            person[i] = int.Parse(reader.ReadLine());
 
        // 오름차순 정렬
        Array.Sort(person);
 
        // 다솜이를 제외한 투표수가 제일 많은 사람과 비교하여 다솜이보다 적으면 0 출력
        if (Dasom > person[N - 2])
        {
            writer.WriteLine(0);
        }
        else
        {
            while (Dasom <= person[N - 2])
            {
                person[N - 2]--; // 제일 투표수가 많은 당선인의 표를 뺃고
                Dasom++; // 다솜이에게 투표수 추가
                count++; // 매수해야되는 사람의 수 증가
 
                Array.Sort(person); // 제일 투표수가 많은 당선인을 찾기위해 Sort
 
                // 다솜이를 제외한 투표수가 제일 많은 사람과 비교하여 다솜이보다 적으면 반복문 종료
                if (Dasom > person[N - 2])
                    break;
            }
 
            writer.WriteLine(count);
        }
    }
 
    writer.Close();
    reader.Close();
}

 

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.