[백준] 1417번: 국회의원 선거(완전 탐색)

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

1417번: 국회의원 선거

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(bf.readLine());	// 후보 수
		int dasom = Integer.parseInt(bf.readLine());	// 다솜이 찍으려는 투표 수
		int[] arr = new int[N-1];	// 각 후보를 찍는 투표 수
		for(int i=0; i<arr.length; i++)
			arr[i] = Integer.parseInt(bf.readLine());
		
		int min = 0;	// 매수해야하는 사람의 최솟값
		if(N == 1) {	// 후보가 자신 혼자인경우
			System.out.println("0");
			return;
		}
		
		while(true) {
			Arrays.sort(arr);
			boolean flag = true;
			int last = arr.length-1;	// 가장 투표가 많은 후보의 인덱스
			// 후보중 가장 높은 투표를 받은 후보가 다솜이의 투표수 이상인경우
			if(dasom <= arr[arr.length-1]) {
				dasom ++;	// 다솜이 투표 +1
				arr[last] --;	// 가장 높은 투표를 받는 후보 -1 
				min ++;		// 한명 매수
				flag = false;	// 다솜이가 당선이 되지 못했으므로 false로 설정
			}
			if(flag)	// 다솜이보다 높은 투표수가 없는경우
				break;
		}
		System.out.println(min);
		bf.close();
	}

}

풀이

다른 후보자의 투표수를 자신의 투표수로 매수를 해서 당선이 되야한다. 

접근방법 : 자신이 당선이 될 때 까지 투표수가 가장 높은 후보자의 투표를 한장씩 매수한다.

 

다솜이의 투표수 - 5

후보자의 투표수 - [7, 4, 8, 10, 9[ 와 같이 있을때. -> [4, 7, 8, 9, 10]

후보자의 투표를 정렬하고, 후보자의 투표 중 가장 높은 투표수(10표)를 가진 후보자부터 한명씩 매수를 한다.

 

다음상황은

다솜이의 투표수 - 6 [한명 매수]

후보자의 투표수 - [4, 7, 8, 9, 9]

마찬가지 가장 높은 투표수를 가진 후보자의 투표 한장을 매수한다.

 

다솜이의 투표수 - 7 [두명 매수]

후보자의 투표수 - [4, 7, 8, 8, 9]

아직 다솜이가 당선이 되지 못했으므로, 위와 동일한 작업을 실행한다.

 

다솜이의 투표수 - 8 [세명 매수]

후보자의 투표수 - [4, 7, 8, 8, 8]

아직도 당선이 되지 못했고, 한명만 더 매수하면 당선이 되기 때문에 총 네명을 매수하면 된다.(최솟값)