[BOJ] 13164 - 행복 유치원

문제 링크

13164-행복 유치원

입력

입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들의 키를 나타내는 N개의 자연수가 공백으로 구분되어 줄 서 있는 순서대로 주어진다. 태양이는 원생들을 키 순서대로 줄 세웠으므로, 왼쪽에 있는 원생이 오른쪽에 있는 원생보다 크지 않다. 원생의 키는 109를 넘지 않는 자연수이다.

출력

티셔츠 만드는 비용이 최소가 되도록 K개의 조로 나누었을 때, 티셔츠 만드는 비용을 출력한다.

문제 풀이

그리디 문제는 진짜 알면 쉽고 모르면 어려운 것 같다..

3개 조로 나누려면 2번 묶어주면 된다는 방식으로 접근
키 순서대로 줄세운 원생들의 키 차이를 새로운 배열에 저장
그 중 키 차이가 덜 나는 n-k개를 묶어버리면 최소 비용

우선 diff 만드는건 당연하게 한 행동인데
그 이후의 과정이 잘 이해가 안되다가
어느 순간 갑자기 아 이건가?싶었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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 tmp = Integer.parseInt(st.nextToken());
        int[] diff = new int[n - 1];

        for (int i = 0; i < n - 1; i++) {
            int height = Integer.parseInt(st.nextToken());
            diff[i] = height - tmp;
            tmp = height;
        }

        Arrays.sort(diff);
        int result = 0;
        for (int i = 0; i < n - k; i++) {
            result += diff[i];
        }
        System.out.println(result);
    }
}