[그리디] 2212. 센서

[BOJ] 2212. 센서

📌 풀이 과정

문제에서 K개의 집중국을 설치할 수 있다고 했을 때, K개의 집중국을 설치하면 K개의 독립된 구간(각각의 구간이 하나의 집중국에 의해 커버되는 구간)을 만들 수 있다.

💡 핵심 아이디어

센서가 쭉 나열되어 있고, 이를 K개의 집중국으로 커버하려고 한다. 각 집중국이 하나의 구간을 담당하게 된다.

• K개의 집중국을 설치할 때, K개의 구간을 만들어야 한다.
• 그 구간을 만들기 위해서는 K-1개의 간격을 끊어야 한다.
• 이때 가장 큰 간격을 끊으면 각 구간의 길이 합이 최소화된다. (즉, 집중국이 커버해야 하는 거리가 최소화된다.)

예를 들어, 센서가 [1, 3, 6, 7, 9]에 위치해 있고, K = 2라면 두 개의 구간을 만들 수 있다. 구간을 나누는 것은 센서 간의 가장 큰 간격(거리가 먼 곳)을 끊는 것이다.

1. 센서 위치: [1, 3, 6, 7, 9]

2. 센서 간의 거리: [2, 3, 1, 2] (이전 센서와의 거리)

   • 이 거리들은 센서 간의 간격을 나타낸다.

3. 가장 큰 간격: 3 (6과 3 사이의 거리)

이제 K = 2의 경우를 생각해 본다. 최대 2개의 구간을 만들 수 있다. 2개의 구간을 만들려면 1번 끊어야 하는데, 어디서 끊는 것이 가장 좋을까?

• 가장 큰 간격인 3을 끊으면, 다음과 같은 두 구간이 생긴다:
  • [1, 3] (첫 번째 구간)
  • [6, 7, 9] (두 번째 구간)

즉, K=2일 때 가장 큰 간격을 제거하면, 나머지 작은 간격들만 남아서 각 집중국이 커버하는 구간의 합이 최소화된다.

👩🏻‍💻 제출 코드

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.StringTokenizer;

/***
 * 2212. 센서
 * 메모리: 16544 KB
 * 시간: 176 ms
 */
public class 센서_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()); // 집중국의 개수
        int[] sensor = new int[N]; // 센서의 좌표
        List<Integer> diff = new ArrayList<>(); // 센서간의 거리 차이

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            sensor[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(sensor);

        for(int i = 0; i < N - 1; i++) {
            int tmp = sensor[i + 1] - sensor[i];
            if(tmp != 0) diff.add(tmp);
        }
        Collections.sort(diff, Collections.reverseOrder());

        int sum = 0;
        for(int i = K - 1; i < diff.size(); i++) { // K-1개 간격 나누기
            sum += diff.get(i);
        }
        System.out.println(sum);

    }

}