BOJ 13164 행복 유치원

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

문제

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

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

---

입력

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

---

출력

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

---

예제 입력 1

5 3
1 3 5 6 10

예제 출력 1

3

---

힌트

• 1조: 1, 3
• 2조: 5, 6
• 3조: 10

---

코드

이전에 이 문제와 비슷한 문제를 풀어본 적이 있는 것 같다.

학생이 N명 있을 때, 학생들의 키 간격은 N - 1개가 있다.

예제에서 키가 1, 3, 5, 6, 10인 학생이 있을 때, 다음 학생과의 키 차이 간격은 각각 2, 2, 1, 4로 4개가 생긴다.

K개의 조로 나눠서 티셔츠 비용을 계산하는 것은 키 차이 간격 중 K - 1개를 제외한 나머지의 간격을 더하는 것이다.

다시 예제로 돌아가 보자.

K가 3이라는 것은 키 차이 간격 중 2개를 제외할 수 있다는 것이다. 최소 비용을 계산하는 것이기 때문에, 가장 간격이 큰 순으로 2개를 제외하면 된다.

문제에 주어진 힌트에서는 2번째와 3번째 학생 사이의 키 차이(2)와 4번째와 5번째 학생의 키 차이(4)를 제외해서 비용을 계산했는데 2번째와 3번째 학생의 키 차이 대신에 1번째와 2번째 학생의 키 차이를 제외해도 같은 키 차이이기 때문에 무방하다.

풀이 방식을 요약하면 다음과 같다.

1. 학생들의 키를 입력받으며, 다음 학생과의 키 차이를 내림차순으로 저장한다.

   실제 구현은 내림차순으로 저장하는 대신에 우선순위 큐를 사용했다.

2. 학생 간의 키 차이 중 가장 큰 K - 1개를 제외한 나머지 키 차이의 합을 최소 비용으로 출력한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    static int K;
    static PriorityQueue<Integer> heightDifferences = new PriorityQueue<>(Comparator.reverseOrder());

    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());
        K = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int lastHeight = Integer.parseInt(st.nextToken());
        for (int i = 1; i < N; i++) {
            int inputHeight = Integer.parseInt(st.nextToken());
            heightDifferences.offer(inputHeight - lastHeight);
            lastHeight = inputHeight;
        }

        int answer = calculateMinCost();
        System.out.println(answer);
    }

    static int calculateMinCost() {
        int cost = 0;

        while (K-- > 1) {
            heightDifferences.poll();
        }

        while (!heightDifferences.isEmpty()) {
            cost += heightDifferences.poll();
        }

        return cost;
    }
}