[boj] 백준 gold5 13164 행복 유치원 (Java) - 그리디

[문제]

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

13164번: 행복 유치원

 

[풀이]

개인적으로 이런 문제가 제일 싫고 제일 어렵다..코드가 복잡하진 않지만 그 로직을 생각해내는게..머리가 핑핑 잘돌아갔으면 좋겠당

 

이 문제의 핵심은 어떻게 최소 비용의 합을 가지는 k개의 그룹으로 묶을 것인지이다. 이를 위해 먼저 모든 인접한 학생들 간의 차이를 구해서 리스트에 넣어줘야 한다.

예제처럼 1 3 4 6 10 의 학생들이 있다고 하면 1번 학생과 4번 학생의 차이는 6-1=5 이다. 그리고 이는 둘 사이의 인접한 학생들의 차이를 더한 것과 같다. 즉 (3-1) + (4-3) + (6-4) = 5 와 같이 구할 수 있다. 

그럼 이 차이를 모두 저장하고 오름차순 정렬 후 k개의 그룹이 만들어질때까지 더해나가면 이는 가장 큰 학생과 가장 작은 학생들의 차이인 비용의 최소 합이 될 것이다.

 

그럼 이제 k개의 그룹은 언제 만들어지는 지를 알아야 한다. n개의 각 그룹이 존재할 때 1번 그룹화를 진행하면 n-1개의 그룹이 남는다. 2번 그룹화를 진행하면 n-2개의 그룹이 남는다. 따라서 n-k번 그룹화를 진행하면 k개의 그룹이 남을 것이다. 이제 n-k번 for문을 돌면서 앞서 정렬해놓은 diff를 더해주면 된다.  

 

[코드]

 

package 그리디;

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

public class boj_13164_행복유치원 {
    static int n, k;
    static int[] heights;
    public static void main(String[] args) throws Exception{
        //K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

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

        Arrays.sort(heights);

        //어떻게 그룹을 묶을 것인가? 
        List<Integer> diff = new ArrayList<>();
        for(int i=1; i<n; i++){
            diff.add(heights[i]-heights[i-1]);
        }

        Collections.sort(diff); //차이 오름차순


        //k개의 그룹을 만들기 위해 n-k번의 합치는 과정이 필요
        int answer = 0;
        for(int i=0; i<n-k; i++){
            answer += diff.get(i);
        }

        System.out.println(answer);
    }
    
}