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

문제

행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다.

이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자.

입력

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

출력

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

예제 입출력

• 예제 입력 1

5 3
1 3 5 6 10

• 예제 출력 1

3

Solution

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int answer = 0;
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] arr = new int[N];
        Integer[] diff = new Integer[N - 1];

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

        for (int i = 1; i < N; i++) {
            diff[i - 1] = arr[i] - arr[i - 1];
        }

        Arrays.sort(diff, Collections.reverseOrder());
        answer = Arrays.stream(diff).mapToInt(Integer::valueOf).sum();

        for (int i = 0; i < K - 1; i++) {
            answer -= diff[i];
        }

        bw.write(String.valueOf(answer));
        bw.flush();
    }
}

어쨌거나 그룹을 만들어야한다. 힌트는 그룹의 인원 수는 아무래도 상관 없다는 것이다.
처음에는 for문 돌려가면서 그룹핑을 해 볼까 싶었지만, 뻘짓이었다.

for (int i = 0; i < N; i++) {
    arr[i] = Integer.parseInt(st.nextToken());
}

for (int i = 1; i < N; i++) {
    diff[i - 1] = arr[i] - arr[i - 1];
}

Arrays.sort(diff, Collections.reverseOrder());
answer = Arrays.stream(diff).mapToInt(Integer::valueOf).sum();

for (int i = 0; i < K - 1; i++) {
    answer -= diff[i];
}

로직은 간단하다. 일단 모든 인원의 키 차이를 구한다.
예제 입력을 예를 들면 다음과 같은 결과가 도출 될 것이다.

원생들 키 : 1 3 5 6 10
키 차이 : 2 2 1 4

K개의 그룹이 생성 된다는 것은 그룹 간에 경계는 총 K-1개 존재한다는 의미다.
즉 가장 키 차이 많이나는 학생들을 경계에 세워버린다.
이게 무슨 의미냐면 그냥 같은 그룹에 배치시키지 않는다는 의미다.
고민 했던 것과는 다르게 쉽게 풀 수 있는 문제였다.