백준 - 13164번, 행복 유치원

[Gold V] 행복 유치원 - 13164

문제 링크

1. 문제 설명

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

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

1.1 입력

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

1.2 출력

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

2. 풀이 논리

1. 학생들을 키를 배열에 담은 후 정렬한다.
2. 키 순으로 정렬된 학생들을 둘 씩 짝지어서 키 차이가 최소가 되도록 한다. 그렇게 키 차이를 리스트에 담아서 이 키 차이값을 정렬한다.
3. 2번까지의 작업이 리스트에 키 차이가 최소가 되는 순으로 그룹핑한 결과를 갖게 한다.
4. 리스트에 담긴 키 차이 값을 몇 번 더해주는 것이 옳은지 판단해보자.

규칙 찾기

1. 둘 씩 짝지어서 만들어지는 키 차이값이 N - 1 개이다.

2. 입력이 N = 5, K = 3로 주어지는 경우, 풀이 논리 2번을 거치면 키 차이값이 4개가 나오는데 그 중에서 2개를 빼야 한다.

   

   

3. 입력이 N = 10, K = 3로 주어지는 경우, 풀이 논리 2번을 거치면 키 차이값이 9개가 나오는데 이 때도 2개만 빼면 되는 규칙성을 볼 수 있다.
   
   

4. 위에서 찾은 2라는 수는 K - 1로 케이스마다 찾을 수 있다!

3. 코드

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

public class Main {
    private static int N, K, answer = 0;
    private static int[] arr;
    private static List<Integer> list = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 원생 수
        K = Integer.parseInt(st.nextToken()); // 조의 갯수
        arr = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        getMinCost();
        System.out.print(answer);
    }

    // K개의 조에 대해 티셔츠 만드는 비용의 합의 최소값을 구하는 메서드
    private static void getMinCost() {
        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++) {
            answer += list.get(i);
        }
    }
}