백준 2212 센서

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

2212번: 센서

도로 위에 N개의 센서가 있고, K개의 집중국이 있습니다. N개의 센서는 1개의 집중국과 반드시 연결됩니다.

이 때 집중국의 수신 가능영역, 즉, 연결되는 센서와의 거리 합의 최솟값을 구하면 됩니다.

(N<=10000, K<=1000)

 

N개의 센서를 먼저 오름차순 정렬 시킨 뒤 센서들의 거리 차를 N-K개 더하면 됩니다.

K개의 집중국을 세울 때 나머지 N-K개 센서가 가장 가까이 있는 집중국에 연결되기 때문에 몇 개 그림 그려보시면 금방 알 수 있습니다.

(처음에 모든 센서의 좌표가 다를 필요 없다는 말을 잘못 해서해 중복을 제거해서 몇 번 틀렸다.)

 

코드는 다음과 같습니다.

(예외 : K>=N 이면 센서에 집중국 다 달면 되므로 정답은 0)