[백준 2212] 센서 - JAVA

문제

문제 정의

집중국을 나누게 되면 나눈 사이의 거리를 제외하고
나머지 왼쪽과 오른쪽에 2와 3이라는 집중국으로 분리됩니다.

---

접근 방법

'어떻게 하면 K개의 그룹으로 센서들을 묶어서,
각 그룹의 양 끝을 잇는 길이의 총합을 최소화할 수 있을까?'

핵심 해결 전략은 센서 사이의 거리가 가장 긴 거리부터 제외하는 것입니다.

예시)

입력

---

1. 센서들을 일직선상에 표현

---

2. 각 센서 사이의 거리를 계산

정렬되었다고 가정하고
왼쪽의 첫 번째 센서와 두 번째 센서 사이의 거리를 0번 인덱스에
두 번째 센서와 세 번째 센서 사이의 거리를 1번 인덱스에..
이런 방식으로 배열을 채워넣습니다.

---

3. 센서 사이의 거리 배열 정렬

위의 배열을 아래와 같이 정렬합니다.

이제 사이 거리가 짧은 순으로 정렬되었습니다.

---

4. 센서 사이의 거리가 가장 긴 거리부터 K-1개를 제거하기

집중국의 수는 $K$입니다.

초기 집중국이 1개이기 때문에
집중국이 $K$가 되려면
$K-1$번 제거해야됩니다.

제거하고 남은 거리들의 합이
$K$개의 집중국의 수신 가능 영역의 길이의 합의 최솟값이 됩니다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static StringTokenizer st;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int K = Integer.parseInt(br.readLine());

        int[] A = new int[N];
        int[] diff = new int[N];

        st = new StringTokenizer(br.readLine());

        if (K >= N) System.out.println(0);
        else {
            for (int i = 0; i < N; i++) {
                A[i] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(A);
            
            for (int i = 1; i < N; i++) {
                diff[i] = A[i] - A[i-1];
            }
            Arrays.sort(diff);

            int answer = 0;
            for(int i = 1; i <= N - K; i++) {
                answer += diff[i];
            }

            System.out.println(answer);
        }
    }
}