[백준] 2212. 센서

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

2212번: 센서

• 그리디 문제로, 2가지 방법으로 풀 수 있다.
• 방법 1: N = 6, K = 2일 때 각 센서 간의 거리들 중 4(N - K)개가 수신 영역이다. 이때 최소한의 수신 영역을 구해야하므로 센서 간의 거리를 오름차순해서 앞에 4개를 더한 것이 답이 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int n;
    static int k;
    static int[] arr;

    public static void main(String[] args) throws IOException {

        n = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        if (k >= n) {
            System.out.println(0);
            return;
        }
        Arrays.sort(arr);

        // 공백 계산
        int[] diff = new int[n - 1];
        for (int i = 0; i < n - 1; i++) {
            diff[i] = arr[i + 1] - arr[i];
        }

        Arrays.sort(diff);

        int answer = 0;
        for (int i = 0; i < n - k; i++) {
            answer += diff[i];
        }
        System.out.println(answer);
    }
}

• 방법 2: N = 6, K = 2일 때 1(K - 1)개의 공백을 두면 된다. 따라서 각 센서 간의 거리를 내림차순해서 앞에 K - 1개를 빼고 나머지 센서 간의 거리를 더하면 된다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int n;
    static int k;
    static int[] arr;

    public static void main(String[] args) throws IOException {

        n = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        if (k >= n) {
            System.out.println(0);
            return;
        }
        Arrays.sort(arr);

        // 공백 계산
        Integer[] diff = new Integer[n - 1];
        for (int i = 0; i < n - 1; i++) {
            diff[i] = arr[i + 1] - arr[i];
        }

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

        int answer = 0;
        for (int i = 0; i < n - 1; i++) {
            if (i >= 0 && i < k - 1) {
                continue;
            }
            answer += diff[i];
        }

        System.out.println(answer);
    }
}