출처: https://www.acmicpc.net/problem/2212
한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였습니다. 각 집중국은 센서의 수신 가능 영역을 조절할 수 있으며, 다음과 같은 규칙을 따릅니다:
각 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타납니다.
N개의 센서는 적어도 하나의 집중국과 통신이 가능해야 합니다.
집중국의 유지비 문제로 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 합니다.
고속도로는 평면상의 직선이며, 센서들은 원점으로부터의 정수 거리의 위치에 놓여 있습니다. 최대 K개의 집중국으로 모든 센서를 커버하는 최소 수신 가능 영역의 길이 합을 구하는 프로그램을 작성하세요.
입력 형식
첫째 줄에 센서의 개수 N이 주어집니다. (1 ≤ N ≤ 10,000)
둘째 줄에 집중국의 개수 K가 주어집니다. (1 ≤ K ≤ 1,000)
셋째 줄에 N개의 센서의 좌표가 공백으로 구분되어 주어집니다.
각 좌표의 절댓값은 1,000,000 이하입니다.
출력 형식
첫째 줄에 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력합니다.
예제 입력 1
6 2 1 6 9 3 6 7
예제 출력 1
5
예제 입력 2
10 5 20 3 14 6 7 8 18 10 12 15
예제 출력 2
7
import java.util.;
import java.io.;
public class Main {
public static int minSensorRange(int n, int k, int[] sensors) {
// 센서 위치 정렬
Arrays.sort(sensors);
// 인접한 센서 간의 거리 계산
ArrayList distances = new ArrayList<>();
for (int i = 1; i < n; i++) {
distances.add(sensors[i] - sensors[i-1]);
}
// 거리를 정렬하여 가장 큰 거리부터 처리
Collections.sort(distances);
// 전체 거리에서 k-1개의 가장 큰 거리를 제외
int result = ____; // 초기 전체 거리
// k-1개의 가장 큰 거리를 제외
for (int i = 0; i < Math.min(k-1, n-1); i++) {
result -= ____; // 가장 큰 거리부터 제외
}
return ____; // 최종 결과 반환
}
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 = Arrays.stream(br.readLine().split(" "))
.mapToInt(Integer::parseInt)
.toArray();
System.out.println(minSensorRange(n, k, sensors));
}
}
빈칸 1 : O
정답: sensors[n-1] - sensors[0]
해설: 초기 전체 거리는 정렬된 센서 배열에서 마지막 센서와 첫 번째 센서의 위치 차이입니다.
빈칸 2 : X
정답: distances.get(distances.size()-i-1)
해설: 정렬된 거리 리스트에서 가장 큰 거리부터 제외해야 하므로, distances.size()-i-1을 사용하여 리스트의 뒤에서부터 접근하며 큰 값부터 처리합니다.
->나는 distances.size()-1 를 선택했다. distances.get(distances.size() - 1)를 사용하면 항상 가장 큰 거리 하나만 참조하게 되므로, k-1개의 거리를 제거하는 루프에서 i 값을 고려하지 않으면 올바른 동작을 하지 않는다.
빈칸 3 : O
정답: Math.max(0, result)
해설: 결과값은 음수가 될 수 없으므로, 0과 비교하여 최대값을 반환합니다.
