문제
백준 2212번 - 센서
아이디어
- 센서의 간격이 최대한 좁은 간격끼리 기지국을 설치하고, 간격이 넓은 구간은 건너뛰는 것이 유리하다.
- 우선 센서를 정렬하여 순서대로 위치하고 하고,
diff
배열을 만들어 센서 간의 간격을 구한다.
- 이
diff
배열을 정렬하여 좁은 간격이 앞에 오게 한다.
- 그리고 앞에서부터
n - k
개의 합이 답이 된다. n - k
개는 간격이 넓은 구간은 건너뛰기 위함이다.
예상 시간 복잡도
코드 구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class BJ_2212 {
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()); //기지국 개수
//1센서 1기지국이 가능한 경우
if (k >= n) {
System.out.println(0);
return;
}
StringTokenizer st = new StringTokenizer(br.readLine());
int[] sensor = new int[n];
for (int i = 0; i < n; i++) {
sensor[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(sensor); //센서 정렬
int[] diff = new int[n - 1];
for (int i = 0; i < n - 1; i++) {
diff[i] = sensor[i + 1] - sensor[i];
}
Arrays.sort(diff); //센서 간의 간격 정렬
int sum = 0;
for (int i = 0; i < n - k; i++) {
sum += diff[i];
}
System.out.println(sum);
}
}