자바

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))