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