백준 13164 행복 유치원 java

그리디 알고리즘

전수민

Nov 21, 2025

TABLE OF CONTENTS

1. 문제에 대하여 📦

문제 링크: https://www.acmicpc.net/problem/13164

애들 일렬로 줄 세움.

줄 서있는 상태에서 애들 그룹으로 묶을 거임

묶인 그룹의 사람 수는 최소 1명 이상이어야 하고, 그 수는 그룹마다 달라도 된다.

그룹마다 티셔츠를 맞출건데, 비용은 그룹 내 제일 큰 사람 - 그룹 내 제일 작은 사람 이다.

모든 그룹의 티셔츠 비용이 최소가 되게 하라.

2. 코드가 나오기까지 🛠️

KEY WORD: 그리디 알고리즘

그룹 내의 키 차이가 많이 날수록 비용이 많이 들므로, 키 차이가 적게 그룹을 나누라는 문제이다.
N명의 학생이 주어지면, 구간은 정확히 N-1개가 나온다.
문제에 주어진 예시를 봐도 인원 수가 5명이니, 구간은 4개가 나오는 걸 볼 수 있다.

이 구간을 K개의 그룹으로 묶을 것이다. 다만 묶는 것을 직접 구현하기 보단, 불필요한 구간을 없애서 연속되는 부분끼리는 묶인 걸로 간주 하는 방식으로 푸는 것이 좋을 것 같다.

K개의 그룹으로 묶을 수 있다는 말은 K개의 덩어리로 나눠야 한다는 말이고 이는 K-1번의 단절이 필요하다는 말이다.
그룹 수가 2개라면 2덩어리로 나눠야 하니 1번의 단절이 필요하다. 그룹 수가 3개라면 3덩어리로 나눠야 하니 2번의 단절이 필요로 된다.
예시에서는 그룹이 3개이다. 따라서 구간 2개를 잘라서 없애고 3개의 그룹을 만들 수 있다.

여기서 이제


그리디 알고리즘

이 나온다.
구간 중 유치원생간의 키 차이가 큰 구간을 최대한 많이 없앤다면, 티셔츠 구매 비용을 절감할 수 있다.

해당 부분을 단절하고 그룹지으면 다음과 같이 3 그룹으로 나눌 수 있고, 비용은 3-1 + 6-5 = 3이다.

(1) 시간복잡도 분석 ⏳

유치원생 배열을 돌아서 키 차이 계산 = O(N)

키 차이 정렬 = O(N-1 logN-1)

그 중 K-1개 빼기 = O(K-1)

따라서 최악의 시간 복잡도는

O( N-1 \times \log{N-1})

이다.

3. 코드 🌐

(1) SUDO CODE 💬


// 간단한 의사 코드

(2) JAVA CODE ☕


import java.util.*;
import java.io.*;
 // b 17255 N으로 만들기
public class Main {
    static int N,K;
    static int [] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        arr = new int [N];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int [] interval = new int [N-1];
        for(int i = 0; i < N-1; i++){
            interval[i] = arr[i+1] - arr[i];
        }
        Arrays.sort(interval);
        K--;
        for(int i = N-2; i >= 0; i--){
            if(K == 0) break;
            interval[i] = 0;
            K--;
        }
        long ans = 0;
        for(int i = 0; i <= N-2; i++){
            ans += interval[i];
        }
        System.out.println(ans);
    }
 }