센서

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

public class B2212 {

    public static void main(String[] args) throws IOException {
        // 입력
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bufferedReader.readLine());
        int K = Integer.parseInt(bufferedReader.readLine());
        List<Integer> sensors = Arrays.stream(bufferedReader.readLine().split(" "))
                .map(Integer::parseInt)
                .collect(Collectors.toList());

        Collections.sort(sensors);
        List<Integer> diff = new ArrayList<>();
        for (int i = 0; i < sensors.size() - 1; i++) {
            diff.add(sensors.get(i + 1) - sensors.get(i));
        }

        Collections.sort(diff);
        System.out.println(diff.subList(0, Math.max(0, N-K)).stream().mapToInt(Integer::intValue).sum());

    }
}

G5

그룹을 어떻게 나누고 최단거리의 합을 어떤 식으로 계산해야 하는가의 아이디어를 생각하기 까다로운 문제였다.

우선 센서 간의 차이를 계산해서 정렬했으면, 그 배열에서 0 부터 N-K 전 까지의 원소들이 바로 최소 거리들이라는 사실을 알아채는 것이 중요하다.

왜냐하면 오름차순으로 차이를 저장한 배열의 원소에 따라서 그룹을 나눌 수 있기 때문이다.

예를 들어보자.
2개의 그룹으로 나누어야 하고 1 6 9 3 6 7 의 센서들이 있다.

센서 배열을 오름차순으로 정렬하면 1 3 6 6 7 9 .
차이 배열을 오름차순으로 정렬하면 0 1 2 2 3 .

여기서 0 ~ 3 (0 ~ N-K-1) 번째에 있는 원소들의 합이 답인 이유는 그룹을 (1,3) / (6,6,7,9) *차이가 가장 큰 3을 기준으로 나눈 그룹
로 나눌 수 있기 때문이다.

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