문제

---

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

코드

---

import java.util.*;
import java.io.*;

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

		// 입력 및 pq 삽입
		int N = Integer.parseInt(br.readLine()) - 1;
		int dasom = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
		for (int i = 0; i < N; i++) {
			pq.add(Integer.parseInt(br.readLine()));
		}

		int count = 0;
		while (!pq.isEmpty() && pq.peek() >= dasom) {		
			++dasom;
			pq.add(pq.poll() - 1);
			++count;
		}

		System.out.println(count);
	}
}

문제 이해

---

• 다솜이가 선거를 조작해서 당선되려고 한다.
• 첫째줄에 사람 인원 수, 둘째줄부터 후보들이 들어온다. 첫번째 후보가 다솜이다.
• 다솜이는 상대 후보에게서 표을 뺏어와서 당선될 수 있다. 이때 필요한 최소 표 수를 구해야 한다.

풀이 방법

---

• MaxHeap(PriorityQueue)에 다솜이를 제외한 모든 후보들의 득표수를 넣는다.
• heap에서 값을 꺼낸 후 다솜이의 득표 수와 비교한다.
• 만약 비교했을 때 후보가 다솜이보다 크거나 같다면, 후보의 득표수를 감소시킨 후 큐에 새로 넣는다.
• 다솜이의 득표수는 증가시키고, count도 증가시킨다.

핵심 포인트

---

• priorityQueue에 넣는 발상까진 쉽게 이해할 수 있다.
• 하지만 값을 꺼낸 후에 주의해야 할 점이 후보자 득표수와 다솜이의 득표수 차이를 계산한 후 더하고 빼면 틀렸습니다.가 나타난다.

  대략 ( 후보 - dasom ) / 2를 하거나 같은 경우엔 1을 빼는 식으로 계산 효율을 높이려 그랬는데, 맞지 않았다.

보완할 점 / 느낀 점

---

• 위에서 언급한대로 pq를 사용하되, 후보자와 다솜이의 차이를 더하고 빼는 방식으로 구현하려 했다.
• 시도했던 대부분의 테케가 맞았음에도 문제가 맞지 않았다. 예상컨데 동점자 처리가 애매한 부분이 있었던 것 같다.
• 어떤 값을 맞추려고 할 때, 1씩 더하고 빼는 방법에 대해서도 알아두어야겠다.

참고자료

---