백준 2212 센서

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

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

public class Sensor {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int K = Integer.parseInt(st.nextToken());
        int[] sensor = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            sensor[i] = Integer.parseInt(st.nextToken());
        }
        if(K>=N){
            System.out.println(0);
            return;
        }
        Arrays.sort(sensor);
        int[] diff = new int[N-1];
        for (int i = 0; i < N -1; i++) {
            diff[i] = sensor[i+1]-sensor[i];
        }
        Arrays.sort(diff);
        int answer = sensor[N-1]-sensor[0];
        for (int i = 0; i < K-1; i++) {
            answer -= diff[N-2-i];
        }
        System.out.println(answer);
    }
}

풀이방법

📢 이문제는 센서의 끝에서 끝 거리에서, 집중국을 세움으로써, 계산하지 않아도 되는 거리가 생긴다는 점이 핵심이다.
<1 3> <6 6 7 9> 집중국이 두개 일때, 이렇게 묶인다.
전체 거리 8에서 계산하지 않아도 되는 거리 3이 생긴 것이다.

이 계산하지 않아도 되는 거리는 K개의 묶음 사이값인 K-1개만큼 생긴다.
이때, 이 사이 거리가 가장 큰 순서대로 전체 거리에서 빼주면 된다.

1. 차이값을 계산하기 위해 센서값을 정렬한다.
2. 차이값을 구해 저장하고, 차이값도 정렬한다.
3. 전체거리에서 K-1만큼 차이값을 큰순서대로 빼준다.

후기

그리디는 알면 간단한데, 이걸 어떻게 떠올려야 하는지를 모르겠다,,