[Baekjoon] 24755_Election Paradox

문제(출처: https://www.acmicpc.net/problem/24755)

---

< Election Paradox >

 

문제 풀이 

 

선거에서 질 수 있는 가장 많은 표를 구하는 방법은 N/2+1개의 도시의 인구수가 적은 지역에서 이기는 것이다. 

만약 입력값이 다음과 같다면

3
11 3 3

 

3명인 지역에서는 1표를 얻고, 11명인 지역에서는 11표를 받으면 된다.

 

my solution (Java)

 import java.io.BufferedReader;
 import java.io.IOException;
 import java.io.InputStreamReader;
 import java.util.Arrays;
 import java.util.StringTokenizer;
 
 public class _24755_ { // Election Paradox
 
 	public static void main(String[] args) throws IOException {
 		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 
 		int N = Integer.parseInt(bf.readLine());
 
 		StringTokenizer st = new StringTokenizer(bf.readLine());
 		int arr[] = new int[N];
 		for (int i = 0; i < N; i++) {
 			arr[i] = Integer.parseInt(st.nextToken());
 		}
 
 		Arrays.sort(arr);
 
 		int result = 0;
 		for (int i = 0; i <= N / 2; i++) {
 			if (arr[i] % 2 == 0) {
 				result += arr[i] / 2 - 1;
 			} else {
 				result += arr[i] / 2;
 			}
 		}
 		for (int i = N / 2 + 1; i < N; i++) {
 			result += arr[i];
 		}
 
 		System.out.println(result);
 	}
 }

변수)
N : 지역 수
arr : 도시 인구수
result : 선거에서 질 수 있는 가장 많은 표

 

지역 수 N을 입력받는다. N만큼 도시 인구수를 입력받아 arr에 저장한다. arr을 오름차순으로 정렬한다.

 

1) 앞에서부터 N/2+1개 지역에서는 선거에서 져야 하므로 절반보다 적게 표를 얻는다.

2) 남은 지역에서는 이겨야 하므로 모든 표를 얻는다.

 

최종 result를 출력한다.

---

---