문제 정리

---

다솜이는 N명의 사람중 국회위원이 되려고 한다
다솜이를 찍을 사람이 다른 모든 국회위원을 찍으려는 사람보다 많아야 한다

예를 들면
다솜이를 찍을 사람이 2명인데
다른 후보 두 명을 찍으려는 사람이 각각 1, 3명일때
다솜이를 찍을 사람이 1, 3명보다 많아져야 한다

다른 후보를 찍으려는 사람들을 돈으로 최소한으로 매수해서 당선되는게 목표이다

입력

총 후보 N명
다솜이의 투표 수
후보 N-1명 각각의 투표 수

출력

다솜이가 매수해야하는 최소한의 사람 수

idea 정리

---

문제를 읽자마자 생각난 문제가 있었다
SWEA 1208 Flatten

높이가 다른 땅을 평탄화 시키는 문젠데 이 문제에서 아이디어를 얻어서 풀었다

다솜이를 제외한 후보자들중
가장 많은 투표를 받을 사람을 골라서 표를 뺏어온다
이 작업을 반복하게 되면 다솜이는 후보자들 중 가장 많은 투표를 받게 된다

알고리즘 구성

---

1. 후보자들의 정보를 받아 다솜이보다 많은 투표수를 가진 후보는 PriorityQueue에 넣는다
   -> PQ는 매번 최다 투표수를 계산하지 않기 위해서 사용
2. pq에서 후보자 정보를 뺀다
3. 다솜이보다 투표수가 많으면 다솜이에게 한 표를 준다 (돈으로 매수)
4. 다시 pq에 넣는다
   -> pq에 후보자 정보를 넣고 빼는 동안 다솜이의 표 수가 바뀌기 때문에 무조건 넣어야함
5. pq에 원소가 아무것도 남지 않을 때까지 2~3 과정 반복
   
   
   주의!
   priority queue를 쓰지 않으면 최소 표를 보장할 수 없다
   

구현

---

//국회의원 선거
public class Main {
	static int N, dasom, res;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		N = Integer.parseInt(br.readLine());
		dasom = Integer.parseInt(br.readLine());
		
		PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
		
		for(int i=1; i<N; i++) {
			int value = Integer.parseInt(br.readLine());
			if(dasom <= value) {     //다솜이보다 투표수가 많은 후보자는 pq에 넣음
				q.offer(value);
			}
		}
		
		while(!q.isEmpty()) {
			int now = q.poll();    //투표수가 제일 많은 후보
			if(now >= dasom) { //다솜이보다 투표수 많으면 한 표 빼고 다시 넣음
				res++;     //매수한 사람의 수
				now--;
				dasom++;
				q.offer(now);
			}
		}
		bw.write(res + "");
		bw.flush();
		bw.close();
		br.close();
	}
}

결과

---