2212 센서 : https://www.acmicpc.net/problem/2212
Problem
Solve
풀이에 접근이 안되서 다른분의 풀이를 봤다.
N개의 센서가 있고 K개의 집중국이 있다.
평면상으로 센서가 있기 때문에 센서의 정수 값이 원점에서 센서까지의 거리이다.
일단 N개의 센서가 있을때 N개의 집중국이 있다면 수신 가능영역 길이는 0이된다.
그렇다면 N개의 센서가 있을때 N-1개의 집중국이 있다면 하나의 집중국이 2개의 센서를 담당하고 나머지 집중국은 센서 하나씩을 담당하면 된다.
이때는 하나의 집중국이 담당하는 2개의 센서의 거리가 가장 짧은 거리여야지 수신 가능 영역의 길이 합이 최소가 될것이다.
그렇다면 각 인접한 센서간의 거리를 구하면 어떤센서 끼리 묶어줘야할지 눈에 보일것이다.
그러기 위해서는 일단 주어진 센서의 위치를 오름차순으로 정렬 한 후, 각 센서의 +1에 위치한 인접 센서와의 거리를 가진 diff 배열을 만들고 내림차순으로 정렬한다(센서간 거리가 먼 순으로).
그 다음은 집중국이 어떤 센서를 담당할지를 정해야한다.
2개의 집중국이 있을때 각 집중국이 담당하는 그룹간에는 1개의 공간이 생긴다.
3개의 집중국이 있을때는 2개의 공간이 생긴다.
즉, K개의 집중국에는 K-1개의 공간이 생긴다는 것이다.
집중국간의 빈공간의 크기는 두 센서간의 거리와도 같다.
그렇다는 것은 diff배열에서 K-1개를 제외한 나머지는 집중국의 범위안에 들어있는 센서간의 거리인것이다.
diff 배열의 앞에서 부터 K-1개를 제외하고 나머지 값의 합이 집중국에 포함되는 센서간의 거리 즉, 수신 가능 영역의 길이의 합이 된다.
Code
public class 센서 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
int K = Integer.parseInt(br.readLine());
int[] sensor = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
sensor[i] = Integer.parseInt(st.nextToken());
}
//거리순 오름차순
Arrays.sort(sensor);
//인접 센서간의 거리
Integer[] diff = new Integer[N - 1];
for (int i = 0; i < N - 1; i++) {
diff[i] = sensor[i + 1] - sensor[i];
}
//거리순 내림차순
Arrays.sort(diff, Collections.reverseOrder());
int answer=0;
//K-1개의 가장 큰 거리를 제외한 거리차이의 합이 수신 가능 영역의 길이 합이된다.
for(int i=K-1;i<N-1;i++){
answer += diff[i];
}
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
}
}
Result
Reference
