[JAVA] 백준 q13164 - 행복 유치원

13164번: 행복 유치원

---

> 의식의 흐름
dfs를 써서 모든 경우에 대해 비용을 구하고 그 중 최소를 뽑으면 되지 않을까? => 시간초과
옆 사람과의 키 차이가 얼마인지 구한 뒤에 차이가 큰 부분을 잘라서 조로 나눠버리면 될 것 같은데..? => 성공

> 풀이 과정
1. 원생의 수(N), 조의 개수(K)를 입력 받는다.
2. 모든 원생의 키를 배열(heights)에 저장한다.
3. 옆 원생과의 키 차이를 배열(gap)에 저장한다.
4. 배열 gap을 오름차순으로 정렬한 후 `N-K`개의 합을 구한다.

# 비용 구하는 방법
5명을 3개 조로 나누는 경우 : (5-3)개의 키 차이 합을 구해야 함.
5명을 1개 조로 나누는 경우 : (5-1)개의 키 차이 합을 구해야 함.
=> N명을 K개 조로 나누는 경우 : (N-K)개의 키 차이 합을 구해야 함.

5. 4번에서 구한 값을 출력한다.

 

> 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static int N, K;
    public static int[] heights;
    public static int[] gap;
    public static int ans = 0;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 원생의 수
        K = Integer.parseInt(st.nextToken()); // 조의 개수

        heights = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++){
            heights[i] = Integer.parseInt(st.nextToken());
        }

        gap = new int[N-1];
        for(int i=1;i<N;i++){
            gap[i-1] = heights[i] - heights[i-1];
        }

        Arrays.sort(gap); // 오름차순 정렬
        for(int i=0;i<N-K;i++){
            ans += gap[i];
        }
        bw.write(Integer.toString(ans));
        bw.flush();
        
        br.close();
        bw.close();
    }
}