[BaekJoon] 1417 국회의원 선거

1.  문제 링크

2.  문제

요약

• 주민들이 누구에게 투표할지 알고 있는 상태에서 기호 1번이 당첨될 수 있도록 다른 기호에게 투표할 사람들을 매수하여 1번에게 투표하도록 할 것인데 이 때, 매수할 사람 수의 최소값을 구하는 문제입니다.
• 입력: 첫 줄에는 후보의 수가 주어지고, 다음 줄부터 기호 번호 오름차순으로 각 후보에게 투표하려던 사람의 수를 입력합니다.
• 출력: 매수하려는 사람의 최소값을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
	public int purchaseNum(ArrayList<Integer> vote_num, int first) {
		if(vote_num.size() == 0) {
			return 0;
		}
		int count = 0;
		while(true) {
			Collections.sort(vote_num);
			if(first > vote_num.get(vote_num.size() - 1)) {
				break;
			}
			first++;
			vote_num.set(vote_num.size() - 1, vote_num.get(vote_num.size() - 1) - 1);
			count++;
		}
		return count;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(br.readLine());
		int first = Integer.parseInt(br.readLine());
		ArrayList<Integer> vote_num = new ArrayList<Integer>();
		for(int i = 0; i < num - 1; i++) {
			vote_num.add(Integer.parseInt(br.readLine()));
		}
		Main m = new Main();
		System.out.println(m.purchaseNum(vote_num, first));
	}
}

4.  접근

• 각 후보들의 투표수 중 기호 1번의 투표수가 가장 높으면 되는데, 그 중 매수하려는 사람을 최소로 해야 하기 때문에 가장 표를 많이 받는 사람에게서 표를 받아오는 방법이 매수하려는 사람을 최소로 할 수 있을 것입니다.
• 그렇기 때문에 가장 표수가 높은 사람에게서 표를 뺏어오고 뺏어올 때마다 투표수를 오름차순으로 정렬하면 계속해서 가장 표수가 높은 사람에게서 표를 뺏어올 수 있을 것입니다.
• 이렇게 진행하다가 가장 높은 표수보다 기호 1번의 표수가 높아지면 이 때, 매수한 사람의 수를 출력합니다.