[Java] BOJ13164_행복 유치원

www.acmicpc.net/problem/13164

13164번: 행복 유치원

---

정렬이 되어 있는 데이터에서 최소를 뽑으려 하는 점에서 그리디를 유추했다.

구하고자 하는 값이 키 차이의 최소이기 때문에 연속된 두 학생의 키 차이를 구해 N-1 크기의 배열을 만들었다.

이 배열에서 작은 키차이를 골라야 하기 때문에 정렬을 하였다.

 

이제 이 키 차이 중 몇개를 골라내야 하는지 알아야 한다.

 

예제의 경우

이런 식으로 나누어지고 [3, 5], [6, 10]의 키 차이가 제외된다는 사실을 알 수 있다.

따라서 K개의 조를 만드려고 할 때 그 조를 나누는 부분이 K-1개가 발생하고 이 만큼의 키 차이를 제외해도 된다는 사실을 알았다.

따라서 정렬된 키차이 배열의 크기인 N-1에서 K-1만큼을 제외한 N-1-(K-1)만큼 뽑아내면 된다. 

 

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		int[] students = new int[N];
		for (int i = 0; i < students.length; i++) {
			students[i] = Integer.parseInt(st.nextToken());
		}
		
		int[] gab = new int[N-1];
		for (int i = 0; i < N-1; i++) {
			gab[i] = students[i+1] - students[i];
		}
		
		Arrays.sort(gab);
		int res = 0;
		for (int i = 0; i < N-K; i++) {
			res += gab[i];
		}
		System.out.println(res);
	}

}