13164 행복 유치원

N명이 주어지고, K개의 그룹으로 나눈 뒤, 각 그룹의 비용 합이 최소가 되어야 한다.

저번에 풀었던 민겸 수 문제처럼 어떠한 규칙이 있을까 해서 규칙 찾는 것을 우선적으로 생각해 봤다.

 

1. 가장 큰 학생부터 왼쪽으로 비교하며, 비용이 커질 때 자른다. -> 결국 끝까지 탐색하지 않으면 원하는 값을 찾을 수 없다.

5 3
1 2 5 6 9 10

탐색
10 -> 9 = 비용1
10 -> 6 = 비용4
...

 

2. 한 그룹에 M명에 들어가는 규칙 찾기 -> 실패

---

 

접근이 잘못된 것 같아 문제를 다시 읽고 생각을 해봤다.

1. 각 그룹의 학생들은 줄에서 인접해 있어야 한다. 따라서 인접한 학생의 연결을 끊으면 그룹이 나뉜다.

i개의 연결을 끊으면 i+1개의 그룹이 나온다.
1 2 5 6 // 9 10

 

2. 학생들의 줄은 오름차순으로 정렬되어 있기 때문에, 인접한 학생일수록 최소의 비용이다.

학생: 1 > 2 > 5 > 6 > 9 > 10
비용:   1   3   1   3   1

(2 > 5) - 비용 3
(2 > 6) - 비용 4

 

이 두 가지를 생각하니 인접한 학생들의 비용을 계산하고 비용이 큰 연결을 끊어주면 각 그룹에서 최솟값이 나오겠다고 생각했다.

N:6, K:3
학생: 1 > 2 > 5 > 6 > 9 > 10
비용:   1   3   1   3   1
여기서 비용이 큰 연결은 2>5와 6>9이다.
따라서 나뉘는 그룹은 (1, 2) (5, 6), (9, 10)이고, 비용은 3이다.

 

N-1개의 비용 리스트에서, K-1개의 최대 비용을 뺀다. -> N-K개의 작은 수를 더해주면 된다.

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] NK = br.readLine().split(" ");
        int N = Integer.parseInt(NK[0]);
        int K = Integer.parseInt(NK[1]);

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int[] costs = new int[N-1];
        int currentStudentHeight = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N-1; i++) {
            int nextStudentHeight = Integer.parseInt(st.nextToken());
            costs[i] = nextStudentHeight - currentStudentHeight;

            currentStudentHeight = nextStudentHeight;
        }

        Arrays.sort(costs);

        int minCost = 0;
        for (int i = 0; i < N - K; i++) {
            minCost += costs[i];
        }

        System.out.println(minCost);
    }
}