백준 2212번 센서 Java

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

문제

---

생각하기

---

• 그리디 문제이다.

동작

어떤 유형인가?

원래 같으면 이분탐색 문제라고 생각했을 문제였다.

하지만 전체 거리에서 가잔 멀리 떨어져있는 부분을 없애면 되는 그리디 문제였다.

Java 배열 역순 정렬, 까먹고 있었는데,

Integer[] 타입으로 해서 Arrays.sort(arr, Collections.reverseOrder()) 해야된다.

K의 범위

K의 범위가 N보다 크다는 조건이 따로 없으므로 K가 N보다 많을 수 있다는 점을 잊으면 안된다.

K가 N보다 크면 당연히 K개의 집중국이 수신 가능 영역의 길이의 합은 0이 된다.

어케 푸나?

센서의 위치를 정렬

각 센서간의 거리차이를 구하고 그 거리를 내림차순으로 정렬.

가장 먼 거리의 차이부터 커버하면 된다.

그리고 K개의 집중국을 설치할 수 있다는건 K개의 구역으로 분리되어야 한다는 것을 의미한다.

6
2
1 6 9 3 6 7

가 입력될 경우

거리차이는 [3, 2, 2, 1, 0]이렇게 된다.

K가 2이기 때문에 2개의 구역이 되기 위해서 K-1개만 선택하면 된다.

그리고 전체 거리의 범위는 1-9이므로 8이 된다. 시작 센서와 가장 먼 거리의 센서

여기서 가장 거리 차이가 먼 센서를 지우면 된다.

결과

코드

---

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

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, K;
    private static int[] arr;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        if(K >= N) {
            sb.append(0);
            return sb.toString();
        }
        Arrays.sort(arr);
        // 차이 역순 정렬

        Integer[] distDiff = new Integer[N - 1];
        for (int i = 0; i < N - 1; i++) {
            distDiff[i] = arr[i + 1] - arr[i];
        }
        Arrays.sort(distDiff, Collections.reverseOrder());

        int dist = arr[N - 1] - arr[0];
        for (int i = 0; i < K - 1; i++) {
            dist -= distDiff[i];
        }

        sb.append(dist);
        return sb.toString();
    } // End of solve()

    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        K = Integer.parseInt(br.readLine());

        arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
    } // End of input()
} // End of Main class