문제
수직선 위에 N개의 센서가 있다. K개의 집중국을 배치하여 모든 센서를 커버할 때, 집중국의 수신 범위 합의 최솟값을 구하라. 각 집중국은 연속된 구간을 담당하며, 각 센서는 반드시 하나의 집중국에 포함되어야 한다.
입력
첫째 줄에 센서의 개수 N이 주어진다. (1 ≤ N ≤ 10,000) 둘째 줄에 집중국의 개수 K가 주어진다. (1 ≤ K ≤ 1,000) 셋째 줄에 N개의 센서 좌표가 주어진다. (0 ≤ 좌표 ≤ 1,000,000)
출력
K개의 집중국이 커버하는 범위의 합의 최솟값을 출력한다.
예제
| 입력 | 출력 |
|---|---|
6 2 1 6 9 3 6 7 | 5 |
풀이
정렬 후 인접한 센서 간의 간격 차이를 이용하는 그리디 방법을 사용한다.
- 센서 좌표를 오름차순으로 정렬한다
- 인접한 센서 간의 차이(diff 배열)를 계산한다
- diff 배열을 오름차순으로 정렬한다
- K개의 집중국이 있으면 K-1개의 "분리 지점"을 만들 수 있다 → 가장 큰 K-1개의 gap을 제거
- 나머지 N-K개의 gap 합이 최솟값이 된다
핵심 아이디어: K개의 집중국으로 커버할 때 최소 범위 합은, 정렬된 센서 사이의 간격 중 가장 큰 K-1개를 "분리 지점"으로 제거하고 나머지 간격의 합이다.
코드
package com.ssafy.an.day199;
import java.io.*;
import java.util.*;
public class Day159BOJ2212그리디알고리즘 { // 2122
static int N, K, ans;
static int[] arr, diff;
public static void main(String args[]) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
K = Integer.parseInt(br.readLine());
arr = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
diff = new int[N - 1];
for (int i = 0; i < diff.length; i++) {
diff[i] = arr[i + 1] - arr[i];
}
Arrays.sort(diff);
ans = 0;
for (int i = 0; i < N - K; i++) {
ans += diff[i];
}
System.out.println(ans);
br.close();
}
}복잡도
- 시간: O(N log N)
- 공간: O(N)