[모각코 23-1] 1회차 - 백준 2212번 센서

* 그리디

중요한 건 집중국을 둘 센서의 위치를 정확히 알아야하는 것이 아니다.

 

전체 코드:

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int sensors = Integer.parseInt(br.readLine());
        int K = Integer.parseInt(br.readLine()); // 집중국
        int[] pos = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        Arrays.sort(pos);
        Integer[] diff = new Integer[sensors-1];
        for(int i=1;i<sensors;i++){
            diff[i-1] = pos[i]-pos[i-1];
        }
        Arrays.sort(diff, (d1, d2)-> {
            return d2 - d1;
        });
        int total=0;
        for(int i=K-1;i<diff.length;i++){
            total += diff[i];
        }
        System.out.println(total);
    }
}

 

예시는 입력 2

10
5
20 3 14 6 7 8 18 10 12 15

를 사용하여 설명한다.

 

int[] pos = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
Arrays.sort(pos);

int[] pos: 입력 세 번째 줄로 들어오는 센서의 위치를 오름차순 정리한다.

 

예)

20 3 14 6 7 8 18 10 12 15 -> 3 6 7 8 10 12 14 15 18 20

 

 

Integer[] diff = new Integer[sensors-1];
for(int i=1;i<sensors;i++){
    diff[i-1] = pos[i]-pos[i-1];
}
Arrays.sort(diff, (d1, d2)-> {
    return d2 - d1;
});

Integer[] diff : 센서의 위치의 차이를 구한다.

* int 배열이 아닌 Integer 를 쓴 이유는 Arrays.sort 내림차순에 람다식을 사용하기 위함

 

예)

int[] pos = {3 6 7 8 10 12 14 15 18 20}

Integer[] diff = {3, 1, 1, 2, 2, 2, 1, 3, 2}

내림차순 sort 후 -> Integer[] diff = {3, 3, 2, 2, 2, 2, 1, 1}

 

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

1. 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력해야 한다.

2. 집중국을 K개 설치한다는 것은, 일직선 상의 센서들에 chunk 를 K-1번 끊는다는 것.

    예) 집중국 5개 -> 3 / 6 7 8 / 10 / 12 14 15 / 18 20

     => 즉 내림차순된 Integer[] diff 에서 K-1 부터 total sum 을 더함