[Algo] 백준 2212 센서 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/16796

메모리 : 16796KB

시간 : 228ms

언어 : Java 11

---

코드

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());
Integer[] arr = new Integer[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
Integer[] cnt = new Integer[N];
cnt[0] = 0;
for (int i = 1; i < N; i++) {
cnt[i] = arr[i] - arr[i - 1];
}

        Arrays.sort(cnt, Collections.reverseOrder());

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

        System.out.println(answer);
    }

}

풀이

문제를 이해하는데 한참 걸렸다. 원점이 존재하고, 원점으로부터 얼마나 떨어져있는지 N개의 수가 주어진다. 최대 K개 만큼의 집중국을 설치해야하고, 집중국이 커버하는 길이가 최소여야한다. 때문에 원점을 중심으로 정렬한 후, 센서 사이의 거리를 구한다. 센서사이의 거리가 멀면 집중국이 커버하는 길이가 늘어나기 때문에 각각 집중국을 설치해 분리하는것이 최적이다. 따라서 센서사이를 정렬하고 가장 먼 센서들부터 K개를 끊어준다고 생각하면 풀이가 쉽다.