[백준][Java] 2212 - 센서

목차

 

문제 정보

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

2212번: 센서

난이도 : G5

유형 : 정렬, 그리디

시간 : O(N + NlogN)

---

문제 풀이

거리를 최소로 만들려면 직관적으로 K만큼 기지국을 설치하면 된다는 것을 알 수 있다.

또한 이문제를 쉽게 이해하기 위해 센서를 K개의 집합으로 나눠서 생각해 보자.

 

[그림1]

빨간 세모 : 센서

빨간색 숫자 : 센서 위치

파란색 숫자 : 바로 옆에 있는 센서와의 거리

 

위 그림에서 기지국 2개를 설치해서 최솟값을 어떻게 구할까?

만약 모든 센서가 바로 양옆에 있는 센서끼리 연결되어 있다고 가정해 보자

만약 기지국이 2개라면 센서들의 연결 부분이 단절되는 선은 1개이다.

만약 기지국이 3개라면 센서들의 연결 부분이 단절되는 선은 2개이다.

---

더 이해가 잘되기 위해 그림을 한번 보자

[그림2]

위 그림처럼 단절선이 1개 생긴다.

이제 감이 좀 올 것이다.

K개의 기지국 있으면 기지국 사이끼리 단절되는 부분이 생길 것이며 이 개수는 K-1개이다.

그럼 단절되는 선들 중 큰 녀석들부터 제외시키면 최소거리를 구할 수 있다. (최솟값을 구하는게 목적이기 때문에)

 

위의 그림의 예시에서 양옆 센서들의 거리의 값들은 [2, 3 , 0, 1, 2]이다.

이 값들을 오름차순으로 정렬하면 [0, 1, 2 ,2, 3]이다.

단절선이 1개이니까 마지막 3를 제외하고 오름차순으로 더해주면

0 + 1 + 2 + 2 = 5라는 최솟값을 얻을 수 있다.

 

더 최적화하는 방법 : K가 N보다 크거나 같으면 바로 0을 출력하면 된다.

---

코드

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

public class Main {

    private int N, K;
    private int[] sensors;
    private int[] diff;
    private int res;

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        K = Integer.parseInt(br.readLine());
        sensors = new int[N];
        diff = new int[N - 1];

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

        Arrays.sort(sensors);

        for (int i = 1; i < N; i++) {
            diff[i - 1] = sensors[i] - sensors[i - 1];
        }

        Arrays.sort(diff);

        res = 0;
        for (int i = 0; i < N - K; i++) {
            res += diff[i];
        }

        System.out.println(res);
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}