문제

아이디어

N = K일 때, 모든 집중국이 센서와 동일한 위치에 존재한다면 집중국의 수신 가능영역의 합은 0으로 최적임이 자명하다.
그렇다면 N = K+1 일 때의 최적해는 어떻게 될까? 가장 가까운 두 집중국을 합친다면 최적이다.
탐욕적인 풀이를 반복한다면 모든 K에 대해서 최적해를 구할 수 있다.

소스코드

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

public class Main {
    static int N, K;
    static int[] sensors;
    static List<Center> centers;

    static class Center {
        int start, end;

        Center(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        K = Integer.parseInt(br.readLine());
        sensors = new int[N];
        centers = new ArrayList<>();

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

        int sensor, totalLength = 0;
        int removeCenter, minDist, curDist;
        for (int i = 0; i < N; i++) {
            sensor = sensors[i];

            centers.add(new Center(sensor, sensor));

            if (centers.size() > K) {
                minDist = Integer.MAX_VALUE;
                removeCenter = 0;

                for (int c = 0; c < K; c++) {
                    curDist = centers.get(c + 1).start - centers.get(c).end;
                    if (curDist < minDist) {
                        minDist = curDist;
                        removeCenter = c;
                    }
                }

                centers.get(removeCenter).end = centers.get(removeCenter + 1).end;
                centers.remove(removeCenter + 1);
                totalLength += minDist;
            }

        }

        System.out.println(totalLength);
    }
}

채점결과