99클럽 코테 스터디 18일차 TIL

백준 - 2212번

집중국의 수신 기능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다.

이 문장이 도저히 이해가 안 돼서 다른 블로그의 그림을 보고 이해했다.

예제 입력 1번

모든 센서는 적어도 하나의 집중국과 연결되어야 한다.

6개의 센서들은 2개의 집중국에 포함되어야 하고, 2개의 집중국 집합으로 나눠보면 위 그림과 같다.

그림의 수신 가능 영역의 합은  2 + 0 + 1 + 2 = 5이다.

1 ~ 6, 7 ~ 9 로도 집합을 묶을 수 있지만 최소 거리를 구해야 하기 때문에 그림처럼 묶었다. 

 

그림을 보면 모든 센서가 각 집중국에 연결되어 있지만 단절되는 부분이 보인다.

단절 부분의 양 옆 센서 거리는 3으로 가장 큰 값을 가지고 있다.

뭔가 보일 듯 말 듯 한데 예제 입력 2번도 그려보자.

예제 입력 2번

센서 개수가 많아 묶을 수 있는 방법도 많다.

0 + 1 + 1 + 2 + 1 + 2 = 7.

센서 3만 독립적으로 구분되었는데 집중국의 수신 가능 영역은 0도 포함한다.

즉, 5개 중 1개의 집중국은 센서 3의 정보만 받아들인다.

 

예제 1번의 단절된 부분은 1개, 예제 2번의 단절된 부분은 4개다.

예제마다 입력된 집중국(k)에서 -1을 했을 때 단절된 개수가 나오고,

단절된 부분의 거리 값을 보면 대부분 다른 센서의 거리 값과 같거나 큰 값으로 구성되어 있다.

 

센서들의 거리 값을 배열(diff)에 저장하고 오름차순으로 정렬하게 되면 큰 값들은 배열 뒷부분에 위치하게 된다.

diff의 개수에서 단절된 부분 개수(k - 1)만큼 빼면 작은 값들만 남게 되어 최소 거리값을 구할 수 있다. 

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

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());

        if (N < K) {
            System.out.println(0);
            br.close();
            return;
        }

        // 센서 좌표 오름차순 정렬
        int[] censors = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < censors.length; i++) {
            censors[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(censors);

        // 센서 거리 차이 - 오름차순 정렬
        int[] diff = new int[N - 1];
        for (int i = 0; i < diff.length; i++) {
            diff[i] = censors[i + 1] - censors[i];
        }
        Arrays.sort(diff);

        int result = 0;
        for (int i = 0; i < diff.length - (K - 1); i++) {
            result += diff[i];
        }

        System.out.println(result);
        br.close();
    }
}

---

백준 2212번- 센서

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

 

참고

https://devteo77.tistory.com/33