[BaekJoon] 2212 센서

1.  문제 링크

https://www.acmicpc.net/problem/2212

2.  문제

요약

• 고속도로 위에 N개의 센서를 설치하는데 예산 상의 문제로 고속도로 위에 최대 K개의 집중국을 세울 수 있습니다.
• 각 집중국은 센서의 수신 가능 영역을 조절할 수 있고 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 됩니다.
• N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 합니다.
• 고속도로는 평면 상의 직선이라 가정하고, 센서들은 원점으로부터의 정수 거리의 위치에 놓여 있습니다.
• 각 센서의 좌표는 정수 하나로 표현됩니다.
• 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 10,000보다 작거나 같은 센서의 개수 N이 주어지고 두 번째 줄에 1보다 크거나 같고 1000보다 작거나 같은 집중국의 개수 K가 주어지며 세 번째 줄에는 절댓값이 1,000,000이하인 N개의 센서의 좌표가 한 개의 정수로 N개 주어집니다.
• 출력: 첫 번째 줄에 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Collections;

public class Main {
	static int[] sensors;
	public int getMinSumOfArea(int office_num) {
		Arrays.sort(sensors);
		Integer[] dif = new Integer[sensors.length - 1];
		for(int i = 0; i < sensors.length - 1; i++) {
			dif[i] = sensors[i + 1] - sensors[i];
		}
		Arrays.sort(dif, Collections.reverseOrder());
		int sum = 0;
		for(int i = office_num - 1; i < dif.length; i++) {
			sum += dif[i];
		}
		return sum;
	}
	
	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 sensor_num = Integer.parseInt(br.readLine());
		int office_num = Integer.parseInt(br.readLine());
		sensors = new int[sensor_num];
		String[] input = br.readLine().split(" ");
		br.close();
		for(int i = 0; i < sensor_num; i++) {
			sensors[i] = Integer.parseInt(input[i]);
		}
		Main m = new Main();
		bw.write(m.getMinSumOfArea(office_num) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 처음에 예제1을 봤을 때
  • 6
  • 2
  • 1 6 9 3 6 7
• 각 센서의 좌표를 오름차순으로 정렬하고
  • 1 3 6 6 7 9
• 집중국을 좌표 2와 7에 설치하여 각각 범위를 1과 2로 주면 답이 3이 되지 않는가 생각하였습니다.
• 그러나 집중국의 수신 가능 영역의 길이는 반지름이 아닌 집중국이 설치된 좌표에서 수신이 가능한 영역의 길이를 말하는 것이었습니다.
• 그렇기 때문에 위 예제에서는 (1, 3)과 (6, 6, 7, 9)으로 묶어 각각이 하나의 집중국과 통신하고 그렇기 때문에 수신 가능 영역의 길이는 (1, 3)에서 2, (6, 6, 7, 9)에서 3이 되기 때문에 총 5가 됩니다.
• 위에서 얘기한 것처럼 주어진 센서들의 좌표를 오름차순으로 정렬하고 각 센서들을 주어진 집중국의 개수만큼으로 묶어 수신 가능 영역의 길이의 합의 최솟값을 구합니다.

• 주어진 센서의 좌표들을 오름차순으로 정렬하고 인접한 두 센서 사이의 좌표의 차이를 구하여 해당 차이값들을 내림차순으로 정렬합니다.
• 두 센서 사이의 좌표의 차이값의 (k - 1)번째 값부터 마지막 값까지 더하여 이를 출력합니다.
  • k개로 센서들을 묶으면 각 묶음 사이에 있는 간격은 수신 가능 영역의 길이의 합에 포함되지 않기 때문에 간격이 큰 (k - 1)개의 값들은 이용하지 않습니다.

1. 주어진 센서의 좌표들을 sensors 배열에 넣고 sensors 배열을 오름차순으로 정렬합니다.
2. 인접한 센서 사이의 차이값을 저장하기 위한 배열 dif를 생성하고 인접한 센서 사이의 차이값을 넣어줍니다.
3. dif 배열을 내림차순으로 정렬합니다.
4. 수신 가능 영역의 길이의 합을 나타내는 변수 sum을 생성하고 0으로 값을 초기화해줍니다.
5. dif 배열의 (k - 1)번째 값부터 마지막 값까지 변수 sum에 더해줍니다.
6. sum값을 출력합니다.