나의 풀이

이전에 한번 풀었었던 문제인데도 20분동안 어떻게 풀지, 무슨 알고리즘 유형의 문제인지 계속 고민했었다...

최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력이라는 부분에서 최대 중에서 최소값을 구해야한다? 라는 생각이 들면서 DP 문제인가 했다가도 어떻게 풀지 도저히 생각이 나지 않았다.

결국 문제를 이해하기 위해 종이를 꺼내들고 테스트 케이스 2개를 직접 그려봤더니... 이해가 됐다.

행렬의 거리를 정렬하고 큰 값 순서대로 k - 1개만큼 없애는 식의 아주 간단한 알고리즘으로 문제가 해결 가능했다.

나의 코드

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

class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int k = Integer.parseInt(br.readLine());
        int[] arr = new int[n];

        if (n <= k) {
            System.out.println(0);
        } else {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }

            Arrays.sort(arr);
            int[] dist = new int[n - 1];
            for (int i = 0; i < n - 1; i++) {
                dist[i] = arr[i + 1] - arr[i];
            }

            Arrays.sort(dist);
            for (int i = 0; i < k - 1; i++) {
                dist[dist.length - i - 1] = 0;
            }

            int answer = 0;
            for (int i = 0; i < dist.length; i++) {
                answer += dist[i];
            }

            System.out.println(answer);
        }
    }
}