[BOJ/JAVA] 백준 2212번 : 센서

2212번: 센서

 

---

 

• 생각

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

 

그리디로 접근을 했다. 센서의 위치를 정렬하고 서로의 인접 거리를 계산한 뒤 기지국을 인접 거리가 긴 위치 순서대로 K개 배치하면 수신 가능 영역의 거리의 합의 최솟값을 구할 수 있게 된다.

 

 

- 예를 들어 N = 6, K = 2 일 경우

 

 

• 코드

정답 코드 : 그리디 방식으로 풀어낸 코드이다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	private static int N, K, answer;
	private static int[] array;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(answer);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;

		N = Integer.parseInt(br.readLine());
		K = Integer.parseInt(br.readLine());
		answer = 0;
		array = new int[N];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++)
			array[i] = Integer.parseInt(st.nextToken());
		Arrays.sort(array);

		int[] temp = new int[N - 1];
		for (int i = 0; i < N - 1; i++) {
			temp[i] = array[i + 1] - array[i];
		}
		Arrays.sort(temp);

		for (int i = 0; i < N - K; i++)
			answer += temp[i];

	}
}