👨‍💻 문제

---

✍️ 풀이

값들이 정렬되어 있기에 그리디로 문제를 해결할 수 있다.

우선 모든 값들을 하나의 조라고 생각한다.
이후 다음 조와 합성하는 비용들을 정리하고,
합성을 진행하며 합성에 사용된 비용을 측정한다.

합성 비용

현재 인덱스의 값과 다음 인덱스의 값의 차이를 담은 배열을 생성한다.

        mergeCosts = new int[N-1];
        for (int i=0; i<N-1; i++) {
            mergeCosts[i] = heights[i+1] - heights[i];
        }

합성

합성 비용을 작은 순서대로 정렬한 이후,
N-K의 횟수만큼 합성을 진행한다.

(N개의 조를 K개의 조로 축소)

        Arrays.sort(mergeCosts);

        int result = 0;
        for (int i=0; i<N-K; i++) {
            result += mergeCosts[i];
        }
        System.out.println(result);

---

📄 전체 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class _13164 {

    private static int N;
    private static int K;

    private static int[] heights;
    private static int[] mergeCosts;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        heights = new int[N];
        for (int i=0; i<N; i++) {
            heights[i] = Integer.parseInt(st.nextToken());
        }

        mergeCosts = new int[N-1];
        for (int i=0; i<N-1; i++) {
            mergeCosts[i] = heights[i+1] - heights[i];
        }

        Arrays.sort(mergeCosts);

        int result = 0;
        for (int i=0; i<N-K; i++) {
            result += mergeCosts[i];
        }
        System.out.println(result);

    }

}

---