(백준) (JAVA) BOJ 2212 센서

질문

한국도로공사는 고속도로를 유비쿼터스화하기 위해 도로를 건설했습니다.

N 센서 설치문제는 이러한 센서에서 수집한 데이터를 수집하고 분석하기 위해 여러 중앙 집중식 스테이션을 설정하는 것이었습니다.

고속도로 K 집결지까지세울 수 있다고 한다.

각 농도 스테이션은 센서의 수신 영역을 조정할 수 있습니다.

에 집중하다 수용 영역은 고속도로의 연결된 도로 구간입니다.

로 표시됩니다 N개의 센서는 적어도 하나의 중앙 집중식 스테이션과 통신할 수 있습니다.

그러나 중앙 집중식 중국의 유지 비용으로 인해 각 중앙 집중식 스테이션의 수신 가능 영역 길이의 합 최소화해야 한다.

귀하의 편의를 위해 고속도로는 비행기 위의 직선이다센서가 이 선의 시작점인 원점에서 정수 거리에 있다고 가정하고 가정해 봅시다.

따라서 각 센서의 좌표는 정수로 표현됩니다.

하다.

이 경우 각 집결지의 수용영역 거리합의 최소값을 구하는 프로그램을 작성하시오. 단계, 집중 스테이션의 수용 영역의 길이는 0 이상이며 모든 센서의 좌표는 다를 필요가 없습니다.

경고하다!
!

1. 중앙 집중식 스테이션의 수신 가능 영역의 길이는 0일 수 있습니다.
   
   (하나의 센서만 수신)
2. 동일한 좌표를 가진 여러 센서가 있을 수 있습니다.
   
   

입력하다

첫 번째 줄에 센서 수 N(1 ≤ N ≤ 10,000)두 번째 줄에 집중 국 수 K (1≤K≤1000)세 번째 줄에 주어진 N 센서의 좌표는 N 정수입니다.

각 좌표 사이에 공간이 주어지면, 좌표의 절대값이 1,000,000보다 작거나 같습니다.

예.

처음에는 컴포지션을 사용하여 해결하려고 했습니다.

k개의 센서를 선택하고 이 위치에 집중 스테이션을 설정하고 집중 스테이션의 수용 영역 길이를 합산합니다.

그러나 컴포지션을 사용하는 경우 O(2^n)의 시간 복잡도를 가지므로 시간 초과를 피할 수 없습니다.

인쇄

첫 번째 줄은 문제에 설명된 최대 K 집중 스테이션의 수신 가능 영역 길이 합계의 최소값을 출력합니다.

10
5
20 3 14 6 7 8 18 10 12 15

7

문제 해결

---

for (int i = 0; i < n; i++) {
	sensors(i) = Integer.parseInt(st.nextToken());
}
Arrays.sort(sensors);

먼저 센서들의 좌표를 받아 배열에 저장하고 배열을 오름차순으로 정렬한다.

샘플 입력 1을 예로 들어

1 3 6 6 7 9

나라가 되다

집결지 접수영역은 좌표평면 우측으로 진행하며,

다음 포커싱 스테이션이 나타날 때까지 두 센서 사이의 거리의 합과 같습니다.

중심국이 좌표평면에서 1, 6에 위치한 경우

첫 번째 집중 장치의 커버리지 영역은 (3 – 1) = 2입니다.

제2 집중 스테이션의 수용 영역은 (6-6)+(7-6)+(9-7)=3이다.

따라서 받을 수 있는 면적의 합은 5입니다.

이 문제의 핵심은 센서 간의 거리를 이용하는 것입니다.

예를 들어 입력값이 1인 센서 사이의 거리를 구하려는 경우

2 3 0 1 2

센서 사이의 거리가 긴 세그먼트를 초과하면 최소값이 아닙니까?

1 3 6 6 7 9
 2 3 0 1 2
A   A

A는 집중국을 의미

첫 번째 센서가 있는 곳에는 무조건 집중 스테이션이 있어야 합니다.

센서간 거리가 긴 부분(k-1)을 생략하여 최소값을 도출할 수 있다.

(위의 예에서 점프 3)

int sum = 0;
// (n - 1): 센서 간 거리를 담을 배열의 크기 (센서 개수 - 1)
// (k - 1): 가장 첫번째 위치는 무조건 집중국을 세워야하므로 이를 제외
for (int i = 0; i < (n - 1) - (k - 1); i++){
    sum += distances(i);	// 센서간의 거리를 더한다
}

그래서 센서 사이의 거리가 포함된 배열을 오름차순으로 정렬한 후,

다음 k – 1 창을 제외한 나머지 요소를 추가합니다.

구현

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main_2212 {

    static int n;
    static int k;
    static int() sensors;
    static int() distances;

    public static void main(String() args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());

        sensors = new int(n);
        distances = new int(n - 1);
        
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            sensors(i) = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(sensors);

        for (int i = 0; i < n - 1; i++) {
            distances(i) = sensors(i + 1) - sensors(i);
        }
        Arrays.sort(distances);

        int sum = 0;
        for (int i = 0; i < (n - 1) - (k - 1); i++){
            sum += distances(i);
        }

        System.out.println(sum);
    }
}

실행결과

---