백준 13164 [자바] java 행복 유치원

문제 링크: https://www.acmicpc.net/problem/13164

13164번: 행복 유치원

 

▶문제

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

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

---

▶입력

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

---

▶출력

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

---

▶해설

문제를 접했을 때 키 순으로 원생들이 주어지므로 일단 인접한 원생들의 값을 구하고 정렬을 해야겠다는 생각을 했습니다. List에 차이를 각각 담고 정렬을 했습니다.

 

그렇다면 구해진 값들을 어떻게 활용할까?? -> 값들은 계산에만 쓰입니다. 중요한 것은 그룹화입니다.

 

한 그룹에 한 명의 원생만 존재한다면 0이므로 그룹에서 나올 수 있는 작은 값입니다. 예시를 보겠습니다.

ex)

5 3

1 3 5 6 10

 

1 3 5 6 10 이 각각 한 그룹이라고 가정합니다.

 

그렇다면 3개의 그룹을 만들려면 가장 작은 차이를 가진 그룹을 2번만 합치면 3 개의 그룹이 완성됩니다. 

 

각 인접한 원생들의 값차이

1,3 -> 2

3,5 -> 2

5,6 -> 1

6,10 -> 4

정렬한다면 1, 2, 2, 4가 됩니다. 

1=5,6 의 차이 2=1,3 or 3,5의 차이

 

정렬된 값을 기준으로 두 번의 그룹을 합치면 됩니다. 그렇다면 5,6이 합쳐지고 1,3or 3,5가 합쳐지고 10은 혼자인 그룹입니다.

 

위에서 나온 2 가지의 경우의 수를 보겠습니다.

{1,3} {5,6} {10} = 3

{1} {3,5,6} {10} = 3

모두 만족합니다. 가장 작은 차이 값들을 그룹의 개수에 합쳐주면 답이 구해집니다. 그룹의 개수는 n-k개를 하면 합칠 횟수를 구할 수 있습니다. (5 3일 때 5개의 개별 그룹을 2번 합치면 3개의 그룹이므로 n-k가 만족합니다.)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {

    static int n, k, result;
    static int[] arr;
    static List<Integer> list = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        k = Integer.parseInt(s1[1]);
        arr = new int[n];
        String[] s = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(s[i]);
        }
        Arrays.sort(arr);
        solve();
        System.out.println(result);
    }

    public static void solve() {
        for (int i = 1; i < n; i++) {
            list.add(arr[i] - arr[i - 1]);
        }

        Collections.sort(list);

        for (int i = 0; i < n - k; i++) {
            result+=list.get(i);
        }
    }
}