백준 2212 센서 (Gold 5)

생각보다 아이디어 생각해내는데 조금 오래 걸림 -> 문제 해석에 시간이 걸림 문제 구현 난이도 자체는 쉬운편
걸린시간 40분 난이도 5/10

/*
	만약에 집중국의 수가 센서수보다 많으면 0이 나온다 
	중복되는 센서 처리 해주기 (처음 초기화 할 때)
	집중국 갯수-1개 많큼 거리를 무시해줄 수 있다 

	original 1 3 6 7 9 	
	diff     2 3 1 2  여기서 집중국이 2개 -> 최댓값 1개 제외가능 

	original 3 6 7 8 10 12 14 15 18 20
	diff      3 1 1 2 2 2 1 3 2 집중국이 5개 -> 최댓값 4개 제외가능 
	sum(dif) = 17 - 10 = 7
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Sensor {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int K = Integer.parseInt(br.readLine());
		
		int[] nums = new int[N];
		int[] diff = new int[N-1];
		
		if(N<=K) {
			System.out.println(0);
			System.exit(0);
		}
		
		String [] input = br.readLine().split(" ");
		for(int i = 0; i < N; i++) {
			nums[i] = Integer.parseInt(input[i]);
		}
		
		
		Arrays.sort(nums);
		
		for(int i = 1; i< N; i++) {
			diff[i-1] = nums[i] - nums[i-1];
		}
		
		Arrays.sort(diff);
		
		int sum = 0;
		for(int i = 0; i < (N-1)-(K-1); i++) {
			sum+=diff[i];
		}
		
		System.out.println(sum);
	}

}