[JAVA] 백준 13164번 : 행복 유치원

 

---

 

• 생각

1. 각각 인덱스 값의 차이를 배열에 저장한 뒤 오름차순 정렬해서 K개 만큼 뽑아내면 될까???

 

• 코드

정답 코드 : i, i+1의 차이의 값을 하나의 배열에 저장해 놓는다. 배열을 오름차순으로 정렬한 뒤 가장 작은 차이를 보이는 값을 N-K만큼 더 해주면 된다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N, K;
    static int[] array, temp;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(FindMinValue());
	}

	private static void SetData() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        array = new int[N+1];
        temp = new int[N-1];
        
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
        	array[i] = Integer.parseInt(st.nextToken());        	
        }
        
        for (int i = 0; i < N - 1; i++)
            temp[i] = array[i + 1] - array[i];
        
        Arrays.sort(temp);
	}

	private static int FindMinValue() {
		int min = 0;		
	    for (int i = 0; i < N - K; i++) min += temp[i];
		
		return min;
	}
}