Q. 2212 : 센서
그리디 (4 of 34)
문제링크
문제
문제
한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다.
각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.
편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표는 정수 하나로 표현된다. 이 상황에서 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. 단, 집중국의 수신 가능영역의 길이는 0 이상이며 모든 센서의 좌표가 다를 필요는 없다.
입력
첫째 줄에 센서의 개수 N(1<=N<=10,000), 둘째 줄에 집중국의 개수 K(1<=K<=1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 이상 있으며, 좌표의 절댓값은 1,000,000 이하이다.
출력
첫째 줄에 문제에서 설명한 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력한다.
예제 입력 1
6
2
1 6 9 3 6 7예제 출력 1
5나의 풀이
접근
백준 문제들의 설명은 하나같이 한 번에 알아들을 수가 없다. 말을 너무 이상하게 한다. 내가 이해한 바로는
기지국 개수가 2개라면 주어진 센서값들을 두 개의 덩어리로 나누는데, 각 덩어리가 좌표상에서 최소한의 범위를 갖도록 해야 한다. 그리고 이 덩어리들의 범위를 구하는 것.
- 주어진 센서 좌표를 배열에 담아 오름차순 정렬
- 배열 값들 간의 차이를 또다른 배열(diff[])에 담고, 이를 내림차순 정렬
- diff[]에서
기지국수 - 1개 만큼의 값을 제외하고 나머지 값들을 모두 더함
java
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int s[] = new int[n];
Integer[] diff2 = new Integer[n-1];
int space = k-1;
int answer = 0;
for (int i = 0; i < n; i++) {
s[i] = sc.nextInt();
}
Arrays.sort(s);
for (int i = 0; i < s.length-1; i++) {
diff2[i] = s[i+1] - s[i];
}
Arrays.sort(diff2, Collections.reverseOrder());
for (int i = space; i < n-1; i++) {
answer += diff2[i];
}
System.out.println(answer);
}
}
리뷰
일반적으로 흔히 쓰는 Arrays.sort() 는 오름차순 정렬이다. 내림차순 정렬을 위해선 Collections.reverseOrder() 라는 옵션을 추가해야 하는데, int[]형 배열은 안되고 Integer[] 형 배열에서만 된다.
어떤 블로그에서는
- int[] 를 Interger[] 로 변환
- Arrays.sort(arr, reverserOrder()); 로 내림차순 정렬
- Integer[] 를 다시 int[] 로 변환
하던데 (int[] 배열을 Integer[] 배열로 변환 (반대 과정 포함/내림차순 정렬)), 이 문제에선 꼭 int[] 를 써야하는 이유가 없으므로 Integer[] 로 선언하여 풀었다.