문제 요약 설명
센서가 x좌표축에 임의의 지점에 주어질 때, 집중국을 k개 설치하여 각 센서들을 관리 해야한다. 이 때에 각각의 집중국들이 관리해야할 범위의 합의 최솟값을 구해야한다. 문제가 조금 어렵게 설명되어져 있는데, 각각의 집중국들이 관리해야할 범위가 꼭 이어져있어야 하는 것은 아니다.
아이디어
집중국을 k개 설치한다고 하는 것은 쉽게 생각하면 센서들이 모여있는 집합이 k개 생성된다고 볼 수 있다. 그 말은 즉슨 센서들을 k개의 집합으로 나누고, 각 집합이 좌표상에서 차지하고 있는 길이(집합에서 가장 오른쪽 센서 - 집합에서 가장 왼쪽 센서)의 합을 구하면 된다. 그림을 그려서 설명하면 다음과 같다.
6개의 센서가 설치되어있고, 2개의 집중국으로 관리해야한다.
센서들이 있는 곳이 빨간색 동그라미라면 센서들 사이의 간격은 초록색으로 적어놓은 숫자라고 볼 수 있다. 예제 입력에서 2개의 집중국이기 때문에 해당 센서들을 두 묶음으로 나누어서 각 묶음의 길이의 합이 집중국의 수신가능영역의 최솟값이다. 그림의 센서들을 두 묶음으로 나누기 위해서는 가장 큰 간격을 제거하면 두 묶음으로 나눌 수 있다. 그렇다면 3 -> 6으로 가는 센서사이의 간격이 가장 크기 때문에 제거한다.
그러면 (1, 3) + (6, 6, 7, 9) 두 묶음으로 센서가 나눠지게 된다. 각 묶음의 길이는
(3-1) + (9-6) 이고 이것은 5가 된다.
즉, 설치해야 하는 집중국이 k개라면 각 센서사이의 간격을 배열에 저장하여 정렬한뒤 해당 배열에서 큰 순서대로 k-1개를 제거하고 나머지 간격합을 다 더하면 답을 구할 수 있다.
=> 간격배열(0, 1, 2, 2, 3) 에서 가장 큰 간격 3을 제거하고 나머지를 더하면
(0 + 1 + 2 + 2) = 5 가 되는 것을 알 수 있다.
풀이
- 입력으로 들어온 센서들 좌표값을 정렬한다.
- 각 센서들 사이의 간격을 gap 배열에 담고 오름차순 정렬한다.
- gap배열에서 큰 순서대로 k-1개의 원소를 삭제한다.
- 삭제하고 남은 원소들을 다 더한다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public 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());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] pos = new int[N];
for(int i = 0; i < N; i++) {
pos[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(pos);
int[] gap = new int[N-1];
for(int i = 0; i < N-1; i++) {
gap[i] = pos[i+1] - pos[i];
}
Arrays.sort(gap);
int sum = 0;
for (int i = N-2-(K-1); i >= 0; i--) {
sum += gap[i];
}
System.out.print(sum);
}
}