2212 센서

문제의 예제를 필기해 보니 13164 행복유치원 문제와 유사해 보였다.

모든 센서를 수신할 수 있는, 최대 K개의 집중국들의 최소 수신 가능영역의 합을 출력하면 된다.

<예제 변형>
5 -> 센서 수
2 -> 최대 집중국 수
1 6 9 3 7 -> 센서의 좌표

좌표: 1 2 3 4 5 6 7 8 9
센서  s   s     s s   s

---

 

각 집중국은 수신 가능 영역을 조절할 수 있기 때문에, 센서들의 길이에 딱 맞춰 설정하는 것이 최솟값일 것이다.

결국, 거리 합이 가장 적은 최대 K개의 센서 그룹을 구하고, 그 길이를 더하면 문제가 원하는 출력이 나올 것이다.

센서: 1 3 6 7 9
차이:  2 3 1 2
=====================
센서: 1 3 /분해/ 6 7 9
차이:  2         1 2
=====================
결국 차이값을 정렬하고 -> 1 2 2 3
N-K만큼 더해주면 된다.-> 1+2+2 => 5

+ 센서의 좌표는 중복 가능하지만, 차이값을 정렬하고 최솟값부터 더해주기 때문에 따로 처리하지 않았다.
<예제 1>
센서: 1 3 6 6 7 9
차이:  2 3 0 1 2
=====================
센서: 1 3 /분해/ 6 6 7 9
차이:  2         0 1 2
=====================
차이값: 0 1 2 2 3
결과값: 0+1+2+2 => 5

---

 

다만, 첫째 줄에 문제에서 설명한 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력한다. 라는 문장이 걸렸다.

• N < K라는 조건이 없었다.
  • K가 N보다 크다면 N-K에서 오류가 생긴다.
  • N개의 센서에서 나올 수 있는 최솟값은 N개의 집중국을 설치하는 것이다. → 거리 합 0
  • 따라서 거리계산 전, K = min(N, K)를 통해 K의 최댓값을 N으로 설정했다.

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {
    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());    // 집중국 수

        int[] sensorPositions = new int[N];
        getSortedSensorPositions(br, sensorPositions);

        int[] distances = new int[N - 1];
        getSortedDistances(sensorPositions, distances);

        K = Math.min(N, K);
        int minSum = 0;
        for (int i = 0; i < N - K; i++) {
            minSum += distances[i];
        }

        System.out.println(minSum);
    }

    private static void getSortedSensorPositions(BufferedReader br, int[] sensorsPosition) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < sensorsPosition.length; i++) {
            sensorsPosition[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(sensorsPosition);
    }

    private static void getSortedDistances(int[] sensorsPosition, int[] distances) {
        for (int i = 0; i < sensorsPosition.length - 1; i++) {
            distances[i] = sensorsPosition[i+1] - sensorsPosition[i];
        }
        Arrays.sort(distances);
    }
}