백준 센서 - 2212 [JAVA] - 23년 1월 9일

1. 주어진 센서 거리가 정렬이 되어 있지 않으므로 x축을 기준으로 정렬
2. 센서끼리의 거리를 구하고 해당 거리를 정렬
3. 거리가 큰 순서대로 정렬하고 jump의 수만큼 거리가 큰 곳을 넘기면 필요한 거리의 합을 구할 수 있다.

※ (기지국의 개수 - 1개) 만큼 거리가 넓은 곳을 넘길 수 있다 => jump

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

//정답 참고 - 센서 [2212]

public class Main {
    static public void main(String[] args) throws IOException {
        BjSolution sol = new BjSolution();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int sensorNum = Integer.parseInt(br.readLine());
        int companyNum = Integer.parseInt(br.readLine());
        String[] sensorDistances = br.readLine().split(" ");
        int[] sensors = new int[sensorNum];
        for (int i = 0; i < sensorNum; i++) {
            sensors[i] = Integer.parseInt(sensorDistances[i]);
        }
        sol.solution(sensorNum, companyNum, sensors);
    }
}

class BjSolution {
    public void solution(int sensorNum, int companyNum, int[] sensors) {
        if (companyNum >= sensorNum) {
            System.out.println(0);
            return;
        }

        //sensor X 거리 기준으로 정렬
        Arrays.sort(sensors);

        int[] sensorDistanceDiffs = new int[sensorNum - 1];

        for (int i = 0; i < sensorNum - 1; i++) {
            sensorDistanceDiffs[i] = sensors[i + 1] - sensors[i];
        }

        int jump = companyNum - 1;

        //정렬
        Arrays.sort(sensorDistanceDiffs);

        int answer = 0;
        for (int i = sensorDistanceDiffs.length - 1; i >= 0; i--) {
            if (jump > 0) {
                jump--;
                continue;
            }

            answer += sensorDistanceDiffs[i];
        }

        System.out.println(answer);
    }
}