[백준 2212번] 센서(자바)

백준알고리즘 2212번 : 센서

 

 

센서가 커버 가능한 수신 가능 영역을 잘 쪼개보니 실마리를 찾을 수 있었다.
센서의 위치를 정렬한뒤, 위치별 차이(즉 센서별 수신이 필요한 영역)를 새로운 배열로 정의한다.
새로운 배열(gap)의 값 중 큰 것부터 집중국의 개수-1 만큼 차감하여 합의 최솟값을 구한다.
(집중국이 1개일때 차감없이 모든 영역을 커버할 수 있다.)


센서의 위치가 각 1 3 6 7 9 라고 한다면
각 센서의 차이는
2 3 1 2 이다.
집중국이 1개일때, 수신 가능 영역의 길이의 합은 2 + 3 + 1+ 2 = 8이다.
집중국이 2개일때, 수신 가능 영역의 길이의 합은 2 + 0 + 1+ 2 = 5이다.
집중국이 3개일때, 수신 가능 영역의 길이의 합은 2 + 0 + 1+ 0 = 3이다.
집중국이 4개일때, 수신 가능 영역의 길이의 합은 0 + 0 + 1+ 0 = 1이다.
집중국이 5개일때, 수신 가능 영역의 길이의 합은 0이다.(모든 센서 위치에 집중국을 하나씩 박는다.)

 

 

 

풀이 과정

---

1. 센서의 위치 배열을 정렬한다.
2. 정렬한 센서간의 위치 차이를 새 배열로 정의한다.
3. 위치 차이 배열을 정렬한뒤, 집중국의 개수 -1 만큼 큰 위치 차이 값을 소거한다.
4. 나머지 위치 차이 값을 더하여 값을 출력한다.

 

 

▽ 정답 소스 보기

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

public class Main {// No2212 : 센서

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int sensor = Integer.parseInt(br.readLine());
        int K = Integer.parseInt(br.readLine());
        int[] pos = new int[sensor];
        int ans = 0;
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < sensor; i++) {
            pos[i] = Integer.parseInt(st.nextToken());
        }

        if (K < sensor) {//집중국이 센서의 갯수 이상이면 수신 가능영역 길이의 최솟값은 0이다.

            int[] gap = new int[pos.length - 1];
            Arrays.sort(pos);
            for (int i = 0; i < pos.length - 1; i++) {
                gap[i] = pos[i + 1] - pos[i];
                ans += gap[i];
            }

            Arrays.sort(gap);

            for (int i = 0; i < K - 1; i++) {
                if (i <= gap.length - 1) {
                    ans -= gap[gap.length - 1 - i];
                }
            }
        }
        System.out.println(ans);
    }
}