[백준] 16678번 모독 JAVA

문제

 

 

---

풀이 방법

예제 케이스와 같이 7 3 6 2 4를 재배치 하면 2 3 4 6 7로 나타낼 수 있다.
한 번의 Defile을 통해 모든 국회위원을 없애기 위해서는 1 2 3 4 5와 같이 1부터 시작해서 각 옆의 수들은  차이가 1 이내여야 한다.

2 3 4 6 7 을 1 2 3 4 5 6 으로 바꾸기 위해서는
7을 1로 만들고(해커 6명 고용)
6을 5로 만들어서(해커 1명 고용) 총 7명의 해커를 통해 1 2 3 4 5 6 을 만들 수 있다.

그러나 가장 뒤의 숫자를 가장 앞의 빈 숫자(1)로 옮기는 과정은 해커를 최소한만 사용하지는 않는다.
1 3 3 5 의 경우 가장 뒤의 숫자를 2로 바꾸면 총 3명의 해커로 1 2 3 3 을 만들 수 있지만
1 3 3 5 에서 3을 2로 바꾸고 5를 4로 바꾸면 총 2명의 해커로 1 2 3 4 를 만들 수 있다.

즉 빈 숫자가 있는 경우 그 숫자 바로 뒤의 숫자를 바꾸는 것이 최소한의 해커를 사용하는 방법이다.

 

 

---

코드 

package ps;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;

public class BOJ_16678 {

	static BufferedReader in;
	static int N;
	static Long[] arr;

	public static void input() throws Exception{
		in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		arr = new Long[N];
		for (int i = 0; i < N; i++) {
			arr[i] = Long.parseLong(in.readLine());
		}
	}

	public static void main(String[] args) throws Exception {

		input();
		Arrays.sort(arr);

		long now = 1;
		long sum = 0;
		for (int i = 0; i < arr.length; i++) {
			// now 미만의 숫자는 이미 박탈당했다.
			if (now > arr[i].longValue()) continue;

			// now 가 1이고 arr[i]가 1이면 0이 더해짐 -> 해커 고용할 필요가 없다.
			// now 가 1이고 arr[i]가 2이면 1이 더해짐 -> 해커 1명을 고용해야 한다.
			sum += (arr[i] - now);
			now++;
		}
		System.out.println(sum);
	}
}