백준 2212 - 센서

Java

2212 번 - 센서

문제

접근 방법

k개의 집중국으로 모든 센서를 커버할 수 있도록, 각 집중국 범위의 합을 구하는 문제이다.

문제의 핵심은 집중국을 어디에 놔두는지 이지만, 집중국의 위치를 구하는 것이 아닌 센서간의 간격의 차이로 범위를 구한다.
집중국을 센서의 위치에만 설치하여야 범위를 최소화 할 수 있으며, 이에 따라 센서간의 간격의 차이가 곧 집중국이 커버 해야하는 범위들이 된다.

이후 범위를 구하는 방법은 다음과 같다.

1. 센서의 거리를 오름차순으로 정렬한다.
2. 각 센서 거리의 차이를 담은 배열을 만든다.
3. 거리차이 배열을 오름차순으로 정렬한다.
4. 거리차이 배열의 0 ~ n-k까지의 합을 출력한다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, result, k;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());
    	k = stoi(br.readLine());

    	int[] arr = new int[n];
    	int[] diff = new int[n - 1];
    	stk = new StringTokenizer(br.readLine());
    	for(int i = 0; i < n; i++) {
    		arr[i] = stoi(stk.nextToken());
    	}
		// 센서를 정렬한다.
    	Arrays.sort(arr);
		// 센서간의 간격을 구한다.
    	for(int i = 0; i < n - 1; i++) {
    		diff[i] = arr[i + 1] - arr[i];
    	}
		// 간격들을 다시 정렬
    	Arrays.sort(diff);
		// 집중국을 설치하지 못한 센서들의 거리를 합한다.
    	for(int i = 0; i < n - k; i++) {
    		result += diff[i];
    	}

    	System.out.println(result);
    	br.close();
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}