Input
- N (1~10,000): 센서의 개수
- K (1~1,000): 집중국의 개수
- 센서의 좌표위치 (정수) N개
Output
K개 집중국 수신가능영역의 최소 길이합
Solve
일직선에 N개의 센서가 있다. 집중국을 K개 세워야 함. 모든 센서는 반드시 집중국의 수신 가능 범위 안에 들어야 함
그 수신 가능 범위를 최소화 하는 문제.
먼저 문제를 이해해보자
예제1
N: 6
K: 2
1 3 6 6 7 9
뭔가 범위의 개념이 좀 내가 생각한것과 다르긴 하지만, 설명하면
1 3 6 7 9
| | | | | | | | |
1~3 -> 2
6~9 -> 3
으로 2 + 3 = 5
정답은 5가 된다.
그럼 이걸 어떻게 알아내는가?
각 집중국이 센서 범위를 얼마나 적게 커버할 수 있냐가 중요하기 때문에, 각 사이사이에 있는 센서들 사이의 거리를 찾아보자.
1 3 6 7 9
| | | | | | | | |
1~3: 2
3~6: 3
6~6: 0
6~7: 1
7~9: 2
거리를 보면 알겠지만 3~6의 범위가 가장 크다. 저기 사이에 집중국을 두면 손해이지 않겠는가?
여기서 생각해볼필요가 있다 집중국이 K개가 주어진다라.. 일단 생각이 잘 안나니, 눈에 보이는대로 찾아보자
집중국이 2개가 주어졌다. K=2
1~3 / 6~6~7~9 합:5 -> (3~6: 3) -> K=2, 1개 제외
이렇게 묶인다. 거리가 3인 부분을 제외하고 묶게되는걸 알 수 있다.
집중국이 3개라면? K=3
1 / 3 / 6~6~7~9 합:3 (1~3:2, 3~6:3 제외) -> K=3, 2개 제외
1~3 / 6~7 / 9 합:3 (3~6:3, 7~9:2 제외) -> K=3, 2개 제외
이렇게 거리가 3인 부분과 2인 부분 중 하나를 골라 제외시킨 상태로 묶이게 되는걸 알 수 있다.
이 사실을 통해 우리는 거리가 긴순서대로 제외시키고 범위를 묶으면 된다는 걸 알 수 있다.
그리고 제외시키는 거리의 개수는 K-1개인것도 알 수 있다. 2개면 1개 제외, 3개면 2개 제외
- 만약 K >= N이면 각 센서에 집중국 하나씩 배치 가능하므로 0을 출력한다.
- 센서의 위치를 입력받아 오름차손 정렬한다.
- 거리배열을 만들어 오름차순 정렬한다.
- K-1개만큼 거리 배열에서 뒤에 있는 값들(범위가 넓은부분) 제외시키고 다 더한다.
Code
import java.io.*;
import java.util.*;
public class BOJ_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());
int[] sensors = new int[N];
int[] diff = new int[N-1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
sensors[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(sensors);
for (int i = 0; i < N-1; i++) {
diff[i] = sensors[i+1] - sensors[i];
}
Arrays.sort(diff);
int sum = 0;
for (int i = 0; i < N-1 - (K-1); i++) {
sum += diff[i];
}
System.out.println(sum);
}
}