[Java] BOJ 2212 센서

[Java] BOJ 2212 센서

 

www.acmicpc.net/problem/2212

2212번: 센서

 

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

public class BOJ_2212_센서 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int K = Integer.parseInt(br.readLine());
		int[] sensors = new int[N];
		int[] diff = new int[N-1];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			sensors[i] = Integer.parseInt(st.nextToken());
		}
		
		if(K == N) {
			System.out.println(0);
			return;
		}
		
		Arrays.sort(sensors);
		
		for (int i = 0; i < N-1; i++) {
			diff[i] = sensors[i+1] - sensors[i];
		}
		Arrays.sort(diff);
		
		int SUM = 0;
		for (int i = 0; i < diff.length-(K-1); i++) {
			SUM += diff[i];
		}
		
		System.out.println(SUM);
	}
	
}

 

그리디는 역시 어렵다....

전혀 아이디어가 떠오르지 않아 다른 코드를 보고 풀었다.

문제이해도 어려웠다.

 

결국 집중국이 센서 사이의 거리를 커버할 수 있어야하는건데 집중국이 K개 라면 센서 사이 거리를 K-1 번 안 더할 수 있다.

그런데 센서와 집중국 수가 같다면 각 센서위치에 집중국을 세우면 되니 모든 과정을 거치기 전에 그냥 0을 출력하고 끝낸다!

 

하지만 N보다 K가 작다면?

위 그림처럼 센서가 5개인데 집중국이 2개라면, 

센서 사이의 거리를 1번 띄어넘을 수 있다.

즉 K개 집중국이 있다면 센서사이 거리를 K-1번 띄어넘을 수 있다.

센서사이 거리를 띄어넘을 떄는 큰 값을 뺴는 게 좋다.

 

그래서, 센서위치를 오름차순 정렬 후

거리 차이를 구해서 배열에 저장하고 오름차순 정렬한다.

 

그리고 거리차이가 큰 애들을 K-1번 뺀다.

 

마지막에 for문에서 i = 0 부터 i < N-K 까지 센서거리를 더한 값이 답인 이유다.

N-K == diff.length(=N-1) - (K-1)