[Java] BOJ2212, 백준 - 센서

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

2212번: 센서

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128MB	5013	2219	1796	43.816%

문제

한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다.

각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.

편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표는 정수 하나로 표현된다. 이 상황에서 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. 단, 집중국의 수신 가능영역의 길이는 0 이상이며 모든 센서의 좌표가 다를 필요는 없다.

 

입력

첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있으며, 좌표의 절댓값은 1,000,000 이하이다.

 

출력

첫째 줄에 문제에서 설명한 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력한다.

 

<풀이>

접근방법부터 함께 생각해보자.

K개의 집중국에서 센서들의 신호를 수신해야한다.

예제의 경우를 생각해보자.

빨간 점이 센서이다.

여기서 한 가지 주의할 점은, 같은 좌표에 있는 센서끼리의 거리는 0이라는 점이다.

 

기지국을 두 개 설치할 수 있으니, 아래와 같이 수신하는 것이 수신가능영역 거리의 합이 최소가 될 것이다.

왼쪽 기지국에서 2, 오른쪽 기지국에서 3의 거리를 수신하여 최소 수신거리는 5가 된다.

 

 

 

개요는 여기까지 하고 문제는 어떻게 해결할 수 있을지 생각해보도록 하자.

기지국이 한 개일때부터 생각해보면 수신가능거리는 무조건 맨 처음 센서부터 맨 끝 센서까지의 거리이다.

이 상태에서 기지국이 하나 더 생긴다고 한다면, 어떤 센서에서 끊어주는게 좋을까?

바로, 센서끼리의 거리가 가장 먼 곳을 기준으로 나눠주면 된다.

위의 예시에서는 [3,6]의 거리가 3으로 가장 멀기때문에, 그 부분을 제외하고 센서를 두 기지국이 나눠서 맡게된다.

그 부분을 제외하고 나눠졌기 때문에, 센서의 수신 범위는 전체 거리에서 그 거리를 뺀 것이 될 것이다.

그렇다면 기지국이 하나 더 생긴다면?

3 다음으로 거리가 먼 [1,3] 구간이나 [7,9]구간을 기준으로 나눠주고 그 거리인 2를 빼주면 될 것이다.

 

여기까지 생각했다면 코드는 쉽게 짤 수 있다.

 

1. 센서의 위치를 입력받은 후, 위치를 기준으로 정렬해준다.
2. 센서끼리의 거리를 저장해준 후, 이 역시 거리를 기준으로 정렬해준다.
3. 총 거리(가장 끝-가장 처음)에서 기지국의 갯수만큼 정렬된 센서 거리를 빼준다.

 

시간복잡도

센서 사이의 거리 구하기: O(N-1)

 

sensor 배열과 diff배열을 정렬

최악의 경우 각각 O(N^2), O((N-1)^2)

 

집중국의 개수만큼 거리 빼주기: O(K)

 

N=10000, K=1000을 기준으로 계산해보면 11000정도 나온다.

 

메모리의 경우도 배열은 20000개정도만 사용하고 복잡한 연산을 사용하지 않기 때문에 여유로울 것

 

 

소스코드

import java.io.*;
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());
		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);

		// 최대거리
		int d = sensor[n - 1] - sensor[0];

		// 센서끼리의 거리의 차이를 저장할 배열
		int[] diff = new int[n - 1];
		for (int i = 0; i < n - 1; i++)
			diff[i] = sensor[i + 1] - sensor[i];

		// 거리 차이를 기준으로 정렬
		Arrays.sort(diff);

		// 센서의 수만큼
		for (int i = 1; i < k && n - 1 - i >= 0; i++) {
			// 가장 큰 거리를 빼준다
			d -= diff[n - 1 - i];
		}

		System.out.println(d);

	}
}