백준 2212번 : 센서 java

이 문제는 문제를 이해하는 것이 어려운 문제였습니다.

이 문제는 N개의 센서가 있고 K개의 집중국이 있는데 K개의 집중국을 이용하여 수신 가능 영역의 길이의 합을 구하는 문제입니다.

이 문제에서 수신 가능 영역이 무엇인지를 설명드리겠습니다.

우선 위 문제의 예제 1번은 다음과 같습니다.

이제 이 센서들을 정렬해보겠습니다.

위의 그림과 같이 나옵니다.

이때 수신 가능 영역이란 아래의 그림과 같이 집중국을 세웠을 때 집중국들에 연결된 구역을 의미합니다.

위의 그림으로 예시를 들면 1 ~ 6까지 5에 7 ~ 9까지 2의 수신 가능 영역을 가져 총 7의 거리입니다.

이때 이 수신 가능 영역을 최소로 만들기 위해서는 두 점 사이의 거리가 가장 먼 곳을 제외하면 됩니다.

위의 그림에서는 3과 6의 거리의 차이가 6으로 가장 멉니다.

따라서 위의 그림과 같이 집중국을 설치하면 5의 수신 가능 영역을 가져 최소의 수신 가능 영역을 설정할 수 있습니다.

이와 같이 N개의 센서와 K개의 집중국이 있으면 N-K개만큼의 간격을 포함해야 합니다.

위의 그림에서는 6개의 센서에 2개의 집중국이 있기 때문에 4개의 간격을 포함하였고, 총 5개의 간격 중 가장 간격이 큰 1개를 제외할 수 있었습니다.

---

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

public 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[] intArr = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i<N; i++)
            intArr[i] = Integer.parseInt(st.nextToken());

        Arrays.sort(intArr);

        Queue<Integer> q = new PriorityQueue<>();
        for(int i = 0; i<N-1; i++)
            q.offer(intArr[i+1] - intArr[i]);

        int ans = 0;
        for(int i = 0; i<N-K; i++)
            ans += q.poll();

        System.out.println(ans);
    }
}

문제를 이해한다면 쉽게 해결할 수 있는 문제였습니다.