[자바/백준 골드5] #13164 행복 유치원

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

 

🔒 골드5 - #13164 행복 유치원 

 

📌 테스트케이스 추가 힌트

4 2
1 4 5 6

= 2

 

✍️ 풀이법

 

한 조에서, 가장 큰 사람과 가장 작은 사람의 차이는 각 조원의 키의 차이의 합과 같다.

 

예로, 위의 예시를 보면 조는 1 / 4, 5, 6 두 개로 나누어지고

두번째 조에서 비용은 (4와 5의 차이) + (5와 6의 차이) 와 같다.

 

따라서 조를 나눌때는, 키 차이가 가장 큰 순으로 조를 나누어야 한다.

 

위 예시에서는 조를 2개로 나누었으므로, 

조원 사이의 거리중 가장 큰 값을 한 개만큼 (= K-1) 지운다. 

 

 

 

 

 

풀이방법:

    1. 다음 사람과의 키 차이를 구한다.

    2. 키 차이에서 큰 값부터 K-1 번째까지를 모두 제외하고 모두 더한다.

 

 

🗝️ 풀이

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class baekjoon13164 {

    static List<Integer> height = new ArrayList<>();
    static List<Integer> heightGap = new ArrayList<>();
    static int K;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        K = sc.nextInt();

        for (int testCase = 0; testCase < N; testCase++) {
            height.add(sc.nextInt());
        }

        solve();
    }

    public static void solve() {

        calHeightGap();
        calCost();
    }

    private static void calCost() {
        int sum = 0;

        for (int j = 0; j < heightGap.size() - K + 1; j++) {
            sum += heightGap.get(j);
        }

        System.out.println(sum);
    }

    private static void calHeightGap() {

        for (int i = 0; i < height.size() - 1; i++) {
            heightGap.add(height.get(i+1) - height.get(i));
        }
        Collections.sort(heightGap);
    }
}