그리디. 센서

문제

N개의 주어진 좌표중 K개의 중심국을 세워 최소 거리를 구한다.

해결방향성

일단 좌표간의 거리를 저장하는 배열 sub[] 를 만든다.
그리고 K개의 중심국을 세워야하므로, 가장 긴거리부터 K - 1개씩 지워준다.
남은 거리들의 합이 세울수있는 기지국의 수와 일치한다.

코드

import java.io.*;
import java.util.*;

public class Main {
    static int N, K;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        K = Integer.parseInt(br.readLine());

        // 센서
        int[] sensor = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            sensor[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(sensor);

        Integer[] sub = new Integer[N - 1];
        for (int i = 0; i < N - 1; i++) {
            sub[i] = sensor[i + 1] - sensor[i];
        }

        Arrays.sort(sub, Collections.reverseOrder());

        // K - 1개 끊음
        int answer = 0;
        for (int i = K - 1; i < N - 1; i++) {
            answer += sub[i];
        }


        bw.write(String.valueOf(answer));

        bw.flush();
        br.close();
        bw.close();
    }


}

결론

정렬을 두번 이용한 문제. 차를 구하기위해 기존 좌표를 오름차순으로 정렬하고, 최소 거리를 제외하기위해 거리를 내림차순으로 정렬한다. 그림을 직접 그려서 다리를 끊듯이 하면 해결되는 문제. 연속적으로 끊을경우 거리가 0인 중심국이 건설되는 셈이다.