[백준] 행복유치원 (자바)

행복유치원

문제 풀이

행복 유치원 문제는 그리디 알고리즘을 사용하여 해결하는 문제입니다.

조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다는 조건이 존재합니다.

이 문제를 해결하기 위해서는 우선 정렬을 해줘야 합니다.

오름차순으로 정렬을 하여 인접한 애들끼리 그룹을 지어야 합니다.

따라서, Arrays.sort()로 오름차순을 한 뒤 차이를 저장하는 배열을 만들어 해당 배열을 사용해 그룹을 나누고 total 값을 합하는 방식을 사용하면 됩니다.

정렬 후 그룹화하는 전형적인 그리디 알고리즘 문제입니다.

풀이 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        // 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다.
        // 최대한 비용을 아끼고 싶어 하는 태양이는 k개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다.

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

        int[] arr = new int[n];

        for (int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int[] sub = new int[n-1];

        // 2 2 1 4
        for (int i = 0 ; i < n -1; i++){
            sub[i] = arr[i+1] - arr[i];
        }

        // 1 2 2 4
        Arrays.sort(sub);

        int total = 0;
        for (int i = 0; i < sub.length - k + 1; i++){
            total+=sub[i];
        }

        bw.write(total+"");

        bw.flush();
        br.close();
        bw.close();

    }


}