[알고리즘 - 백준] 행복 유치원(java)

백준 - 행복 유치원 문제 링크

이 문제는 그리디 문제로, 키 순서대로 나열된 학생들의 키를 입력받고 그 중 그룹마다 키 차이의 합 중 가장 작은 값을 구하는 문제다. 위의 예시대로 5명(N=원생의 수)을 3개의 조(k)로 나누어야 하지만, 각 조마다 최소 한명씩은 있어야 한다.

인접한 키 차이를 구해보면

1 3 5 6 10

2 2 1 4

로 구할 수 있다. 하지만 각 조에서 가장 큰 키와 가장 작은 키의 차이가 최소가 되도록 해야하므로 키를 내림차순 정렬하고 k-1개(문제에서는 2개가 되겠다)만큼 앞에서부터 없애고 나머지 키 차이들만 합해주면 합의 최솟값이 구해짐을 알 수 있다.

따라서 2와 1이 남으므로 합인 3이 답이다.

4 2 2 1로 내림차순 정렬이 되어있을 때 3개(k개) 그룹으로 나누려면 2개(k-1개)의 구분선만 있으면 된다. 다시말해서
1 | 3 5 | 6 10 이나 1 3 | 5 6 | 10 이렇게 k-1개의 구분선만 있으면 k개의 조로 나눌 수 있다는 말이다. 따라서 키 차이가 나는 곳 중 가장 큰 k-1개에 구분선만 놓아주면 합의 최솟값을 구할 수 있다는 말이 된다.

코드

import java.util.*;
import java.io.*;
class Solution{
	static int n, k, arr[];
	public static void main(String args[]) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine(), " ");
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		arr = new int[n];
		
		PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
		
		st = new StringTokenizer(br.readLine(), " ");
		for(int i=0;i<n;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		for(int i=0;i<n-1;i++) {
			pq.add(arr[i+1]-arr[i]);
		}
		
		
		for(int i=1;i<k;i++) {
			pq.poll();
		}
		
		int sum = 0;
		int size = pq.size();
		for(int i=0;i<size;i++) {
			sum += pq.poll();
		}
		
		System.out.println(sum);
	}
	
}