[백준 2212 /JAVA] 센서

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

2212번: 센서

 

집중국을 어디다가 놔둬야 하는지 알아내는 것이 중요한 문제이다.

센서들을 거리에 맞게 정렬하고 사이거리를 구한다.

사이거리가 긴 부분을 제외하고 집중국을 설치하도록 한다.

 

예제 1번에서 센서를 거리에 맞게 정렬하면 1 3 6 6 7 9 이다

각 사이 거리는 2 3 0 1 2 인데 2개의 집중국을 설치해야한다면 딱 한 센서 사이를 기준으로 나누면 된다.

즉, 사이 거리가 3인 부분을 기준으로 나눈다.

1 3 / 6 6 7 9 로 나눈다.

 

예제 2번도 같다. 센서를 거리에 맞게 정렬하면 3 6 7 8 10 12 14 15 18 20이다.

각 사이 거리는 3 1 1 2 2 2 1 3 2 인데 5개의 집중국을 설치해야 한다면 4개의 사이를 기준으로 나눠야 한다.

가장 긴 3 두 개와 2 두 개를 제외하면 된다.

2를 선택하는 것은 아무거나 선택하면 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
    static int N, K;
    static int[] a;
    static Integer[] b;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        K = Integer.parseInt(br.readLine());

        a = new int[N];
        b = new Integer[N - 1];

        String input = br.readLine();
        StringTokenizer st = new StringTokenizer(input);

        for (int i = 0; i < N; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        //오름차순 정렬
        Arrays.sort(a);

        //사이 거리 구하기
        for (int i = 0; i < N - 1; i++) {
            b[i] = a[i + 1] - a[i];
        }

        //거리 오름차순 정렬
        Arrays.sort(b);

        int result = 0;

        //가장 큰 K개 사이 거리 빼고 합 구하기
        for (int i = 0; i < N - K; i++)
            result += b[i];

        System.out.println(result);

    }
}

먼저 입력 받은 센서를 오름차순으로 정렬하고 각 사이 거리를 구한다.

사이 거리도 오름차순으로 정렬하고 가장 큰 K개를 제외하고 더해준다.