백준 2212번: 센서

백준 2212번: 센서

- 그리디 알고리즘과 정렬을 이용하는 문제입니다.

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

 

좌표 3과 6에 센서를 설치하면 2 + 3 = 5로 최솟값이 됩니다. 5 = 0 + 1 + 2 + 2 입니다. 이를 일반화 해보면 다음과 같습니다.

1. 센서의 좌표를 입력 받은 뒤, 오름차순으로 정렬합니다.
2. 각 센서 간의 거리를 구합니다.
3. 센서 간의 거리를 오름차순으로 정렬합니다.
4. 0번 index부터 n-k-1번 index까지의 총합을 구합니다.

 

 

	import java.util.*;
	import java.io.*;
	public class Memo{
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st;
	int n = Integer.parseInt(br.readLine());
	int k = Integer.parseInt(br.readLine());
	int[] a = new int[n];
	int[] sub = new int[n-1];
	st = new StringTokenizer(br.readLine());
	for(int i = 0; i < n; i++){
	a[i] = Integer.parseInt(st.nextToken());
	}
	Arrays.sort(a);
	for(int i = 0; i < n-1; i++){
	sub[i] = a[i+1] - a[i];
	}
	Arrays.sort(sub);
	int sum = 0;
	for(int i = 0; i < n-k; i++){
	sum += sub[i];
	}
	System.out.println(sum);
	}
	}

view raw BOJ_2212.java hosted with ❤ by GitHub