[백준] 2212 - 센서

[문제링크]

2212번: 센서

 

0. 센서의 위치가 아닌, 센서 사이의 거리에 대한 문제이다

 

1. 센서가 N개 있다면, 센서 사이의 거리는 N-1개 생성된다

 

2. 기지국이 1개라면, 해당 기지국은 모든 거리를 포함해야한다

 

3. 기지국이 2개라면, 어떤 거리 X를 이루는 두 센서를 각각 관리함으로서, 거리 X부분을 포함하지 않아도 된다

 

4. 기지국이 K개라면, N-1개의 거리들 중 K-1개를 선택하지 않아도 된다

 

5. 전체 거리들 중 그 값이 큰 순서로 K-1개 선택하지 않으면 요구한 최소 길이의 합이 나온다

 

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = pint(br.readLine());
		int K = pint(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int minimumArea=0;
		
		int[] sensor = new int[N];
		PriorityQueue<Integer>pq = new PriorityQueue<>();

		for (int i = 0; i < N; i++) {
			sensor[i] = pint(st.nextToken());
		}
		
		Arrays.sort(sensor);
		
		for (int i = 1; i < N; i++) {
			int distance = sensor[i]-sensor[i-1];
			pq.add(distance);
		}
		
		
		for (int i = 0, len=pq.size(); i < len - (K-1); i++) {
			minimumArea+=pq.poll();
		}
		System.out.println(minimumArea);
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}

결과 화면