[자바]백준 1417번 국회의원 선거 [그리디][엄탱]

안녕하세요. 개발자 엄탱입니다.
이 글은 알고리즘을 공부하면서 공부 기록용입니다.
그래서 설명마다 일기용으로 편하게 작성하여 반말 형식으로 작성하려고 합니다.
그리고 보시다가 더 좋은 방법이나 잘 못 알고 있는 내용이 있다면 알려주시면 정말 감사하겠습니다.
좋은 하루 되세요 :)

 

그리디는 제일 쉬운 알고리즘이라고 하던데, 나는 그리디가 너무 어렵다 ㅠㅠㅠ 오히려 그래프 최단 경로, 최소 신장 알고리즘이 처음에 접하는 게 어렵더라도 문제가 정형화되어있는 느낌인데, 그리디는 정말... 어떨 때는 A 어떨 때는 Z 아 ~ 그래도 A ~ Z 나오는구나 싶어서 또 문제를 풀려고 하면 갑자기 *(&^%$%$%^&%& 같은 처음 보는 형식의 문제가 나와 정말 당황스러운데 다른 사람들이 어떻게 풀었는지 보면 그냥 단순한 게 최고인 경우도 있고 너무 복잡하게 생각해도 안 좋은 것 같다가도 쉽게 생각이 안 나 다시 복잡하게 생각하고 어렵다 어려워

 

문제

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

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

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

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

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

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

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

 

입력

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

출력

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

 

예제

 

문제 설명

해당 문제는 간단하게 설명해서 다솜이가 국회의원에 당선되기 위해 후보들의 표를 최소로 가져와 1등이 되어 국회의원이 되냐의 문제다.

즉, 몇개의 표를 훔쳐오면 되냐는 문제이다.

 

해설

나는 처음에 정렬과 반복문을 한 번만 사용하여 풀려고 이것저것 해보다 실패했다.

하지만 이 문제는 단순하게 생각해서 단순한 방식으로 풀 수 있는 문제였다.

다솜이의 표보다 많은 후보 중에, 가장 높은 표를 갖고 있는 사람한테 1표씩 뺏어서 다솜이의 표로 만들면 된다.

나는 위의 방식을 우선순위큐를 사용해서 구현했다.

 

해설(내가 접근 했던 방식 - 생략 가능)

내가 처음에 접근한 방식은, 후보들 표 오름차순 후에 다솜이의 표보다 많으면 1표씩 뺐고 마지막 후보의 표만 균형 있게 뺐으면 되겠다 싶었지만 아래와 같은 반례가 있었다.

5

2

3

4

5

100

 

그 다음으로는 가장 많은 사람 표부터 균형 있게 뺐고 그다음 하고 비교해서 균형 있게 뺐으면 되는 줄 알았지만,

3

5

7

7

같은 경우에는 7이 아닌 8과 같이 오답이 출력되었다.

 

그래서 가장 단순하게 그냥 많은 사람을 맨 앞에 새우고 그 사람 표를 하나씩 뺐어서 다시 많은 사람의 표를 하나씩 뺐고 결국 표가 가장 많은 사람보다 다솜이의 표가 많으면 뺐은 표의 수를 출력하면 된다. 

 

코드

import java.io.BufferedWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        int ans = 0;
        int first = Integer.parseInt(br.readLine());
        
        PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);
        
        for (int i = 0; i < T - 1; i++) {
            pq.offer(Integer.parseInt(br.readLine()));
        }
        
        while(!pq.isEmpty() && first <= pq.peek()) {
            ans++;
            first++;
            pq.offer(pq.poll() - 1);
        }

        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}