import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
public class sensor_2212 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int K = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
ArrayList<Integer> sensors = new ArrayList<>();
for (int i = 0; i < N; i++){
sensors.add(Integer.parseInt(st.nextToken()));
}
if (K >= N) {
System.out.println(0);
return;
}
Collections.sort(sensors);
ArrayList<Integer> diff = new ArrayList<>();
for (int i = 1; i < N; i++) {
diff.add(sensors.get(i) - sensors.get(i-1));
}
Collections.sort(diff);
Collections.reverse(diff);
int res = sensors.get(sensors.size()-1) - sensors.get(0);
for (int i = 0; i < K-1; i++){
res -= diff.get(i);
}
System.out.println(res);
}
}
이 코드는 감지 센서의 위치를 최적화하는 문제를 해결하는 자바 알고리즘입니다. 감지 센서들은 일렬로 놓여져 있으며, 각 센서를 커버하는 클러스터의 수를 최소화하는 것이 목표입니다.
먼저, 센서의 수(N)와 설치할 수 있는 기지국의 수(K)를 입력받습니다.
그 다음, 각 센서의 위치(sensors)를 입력받습니다.
만약 설치할 수 있는 기지국의 수가 센서의 수보다 많거나 같다면, 모든 센서를 각각 하나의 기지국으로 커버할 수 있으므로, 0을 출력하고 프로그램을 종료합니다.
센서들의 위치를 오름차순으로 정렬합니다.
인접한 센서들 간의 거리 차이를 계산하고(diff), 이 차이들을 내림차순으로 정렬합니다. 이렇게 하면 가장 큰 거리 차이부터 처리할 수 있습니다.
res는 가장 오른쪽 센서와 가장 왼쪽 센서 간의 거리를 나타내며, 이 값은 최대 커버 가능 거리입니다.
그 다음, 가장 큰 거리 차이부터 (K-1)개의 차이를 res에서 빼줍니다. 이 과정은 기지국이 커버하는 거리를 최소화하는 방법으로, 가장 거리 차이가 큰 구간부터 기지국을 설치해 나가는 것을 의미합니다.
모든 기지국을 설치한 후, 그때까지의 최소 커버 가능 거리(res)를 출력합니다.
이 알고리즘은 각 기지국이 가능한 한 많은 센서를 커버할 수 있도록 설치되도록 합니다. 이를 위해 가장 거리 차이가 큰 센서부터 기지국을 설치하고, 결과적으로 각 기지국이 커버하는 전체 거리를 최소화합니다.
import sys
input = sys.stdin.readline
N = int(input())
K = int(input())
sensor = list(map(int, input().split()))
sensor.sort()
if K >= N:
print(0)
sys.exit()
distances = []
for i in range(1, N):
distances.append(sensor[i] - sensor[i-1])
distances.sort()
for _ in range(K-1):
distances.pop()
print(sum(distances))