[백준] 13164 행복 유치원 - 그리디 JAVA

https://www.acmicpc.net/problem/13164

13164번: 행복 유치원

 

코드설명

그리디 문제입니다.

 

입력예시로 설명해보겠습니다.

입력값
5 3
1 3 5 6 10

문제조건에 의하여 항상 원생들은 인접해야한다는 조건이 있으므로, 인접한 유치원들의 키차이를 구합니다.

키 차이
2 2 1 4

우리는 키 차이가 최소가 되게 만들어야합니다. 

 

그렇기 위해서 오름차순으로 정렬합니다.

키 차이 오름차순 정렬
1 2 2 4

여기서 1과 2의 차이를 가지도록 설정하고, 2와 4 는 차이를 가지지 않도록 처리해야합니다.

그러므로, 2 와 4 는 합연산에 들어가면 안된다는 의미입낟.

즉 1 + 2로 답은 3 입니다.

 

여기서 우리가 구한 차이의 개수들은 N - 1 개입니다. 위의 예시에서는 N = 4이므로 차이의 개수는 3개입니다. ( 2 2 1 4 )

우리가 구하고자하는 그룹의 개수는 3개입니다. ( 문제조건에서 K = 3 이라고 나와있습니다. )

1 2 2 4 가 있을때 3개의 그룹으로 나눌려면, 2개의 구분선이 있으면 가능합니다.

예시로는, 1 3 ★ 5 6 ★ 10   (여기서 별이 구분선 입니다. ) 

보시다시피, 3개의 그룹을 만들려면 2개의 구분선이 필요한걸 알 수 있습니다. 즉, K - 1 개의 구분선이 필요한 것입니다.

 

문제에서 구분선을 구하기 위해서는 우리가 구한

키 차이 오름차순 정렬
1 2 2 4

• 4 개 중에서 2개를 정하면, 그게 최소의 비용일 것 입니다. ( 남은 2개는 구분선이 되어서 더해지지 않습니다. )

즉, 위의 4 길이의 차이배열에서 결국 최소값의 2개만 선택한다는 의미입니다.

수학적으로 보면,

키차이의 개수를 구하면, N - 1 개입니다. (5개의 입력값에서는 4개의 차이의 배열이 나옵니다.)

구분선의 개수를 구하면, K - 1 개입니다. (3개의 그룹을 가지려면, 2개의 구분선으로 그룹을 나눕니다.)

즉, (N - 1) - ( K - 1 ) 개. N - K 개의 차이배열만 더해주면 해당 값이 최소입니다.

 

코드

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


public class Main {
	
	public static int N,K;
	public static int[] arr;
	public static int[] arr_diff;
	public static int answer =0 ;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	K = Integer.parseInt(st.nextToken());
    	arr = new int[N];
    	arr_diff = new int[N-1];
    	
    	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++) {
    		arr_diff[i] = arr[i+1] - arr[i];

    	}
    	Arrays.sort(arr_diff);
    	
    	for(int i=0;i< (N-1) - (K-1); i++) {
    		answer += arr_diff[i];
    	}
    	System.out.println(answer);

    }
}