[Baekjoon] 2212번: 센서

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

2212번: 센서

문제 설명

고속도로에 센서들이 설치되어 있다. 그리고 이 센서들 사이에 집중국을 세워서 센서에서 얻은 데이터를 처리한다고 한다. 최대 K개의 집중국을 설치할 수 있다고 할 때 각 집중국의 수신 가능영역 거리의 합의 최솟값을 구하는 프로그램을 작성해야 한다.

처음 문제를 보면 무슨 말인지 잘 모를 확률이 높으니 예제 입력 1을 가지고 그림으로 보자.

주어진 센서는 위와 같이 배치되며 여기에 K개의 집중국을 수신 가능영역 거리의 합의 최솟값이 되도록 배치해야 한다는 것이다.

풀이 방법

예제 입력 1을 가지고 설명을 이어나가겠다.

주어진 센서가 [1, 6, 9, 3, 6, 7] 이므로 직선 상에 위와 같이 배치된다. 이제 여기에 K개, 즉 2개의 집중국을 수신 가능영역 거리의 합의 최솟값이 되도록 배치해야 한다. 이를 위해서는 먼저 센서들 간의 거리를 알아야 한다.

각 센서들간의 거리를 계산해보면 다음과 같다.

• 1 ~ 3 = 2
• 3 ~ 6 = 3
• 6 ~ 6 = 0
• 6 ~ 7 = 1
• 7 ~ 9 = 2

 

그럼 당연히 이 거리가 짧은 곳들에 설치해야 합이 최소가 될 것이다. 이 거리를 기반으로 집중국을 설치하면 다음과 같다.

집중국 1개는 1 또는 3에, 그리고 나머지 1개는 6에 설치하는 것이 거리의 합을 가장 짧게 구성할 수 있다. 그렇다면 이 거리의 합은 어떻게 구할까? 우리는 이를 먼저 구해놓았다.

1 ~ 3 사이의 센서 거리는 2, 6 ~ 9 사이의 센서 거리는 0 + 1 + 2이다. 이 센서 거리를 모두 더하면 2 + 0 + 1 + 2 = 5가 되고 이것이 이 문제의 정답이 된다.

 

이 문제를 코드로 풀자면 핵심은 정렬이다. 먼저 입력받은 센서들을 오름차순으로 정렬한 배열을 만든다. 그리고 각 센서들 간의 거리를 계산한 배열을 하나 더 만들고 이 또한 오름차순 정렬한다. 그리고 나서 거리 차이 배열을 (센서 개수(N) - 집중국 개수(K)) 만큼 반복하면서 그 합을 더하면 정답을 구할 수 있다. N - K를 하는 이유는 다음과 같다.

• 만약 K가 N과 같다면 센서마다 집중국을 설치하면 결과는 0이 될 것이다.
• K가 N - 1이라면 거리가 가장 짧은 센서에 있는 집중국을 빼야 한다.
• K가 N - 2라면 거리가 가장 짧은 센서에서 2개만큼 집중국을 빼야 한다.

 

이런 식으로 계산되기 때문에 N - K가 합을 구할 때 반복의 조건이 된다.

코드는 다음과 같다.

import java.io.*;
import java.util.*;

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[] sensors =
                Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        Arrays.sort(sensors);

        int[] diffs = new int[N - 1];
        for (int i = 0; i < N - 1; i++) {
            diffs[i] = sensors[i + 1] - sensors[i];
        }

        Arrays.sort(diffs);

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

        System.out.print(answer);
    }
}