[13164] 행복 유치원

🔗 문제 링크

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

🔍 문제 설명

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

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

⚠️ 제한사항

•  1 ≤ N ≤ 300,000

• 1 ≤ K ≤ N

• 원생의 키는 $10^9$ 를 넘지 않는 자연수이다

🗝 풀이 (언어 : Java)

n - k 번 합쳐야 k개의 그룹이 완성된다. 키 순으로 줄 선 원생들의 인접 학생과 차이를 구하고, 차이가 작은 순으로 정렬한다. 차이가 작은 순의 값들을 n - k 번 합산해주면 정답이다.

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(), " ");
        StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
        br.close();
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[] children = new int[n];
        for (int i = 0; i < n; i++) {
            children[i] = Integer.parseInt(st2.nextToken());
        }
        solution(k, children);
    }

    private static void solution(int k, int[] children) {
        long answer = 0;
        int[] diff = new int[children.length - 1];
        for (int i = 0; i < children.length - 1; i++) {
            diff[i] = children[i + 1] - children[i];
        }
        Arrays.sort(diff);
        for (int i = 0; i < children.length - k; i++) {
            answer += diff[i];
        }
        System.out.println(answer);
    }

}