BOJ 13164 행복 유치원 (Java)

문제 탐색하기

• 총 N명의 원생이 K개의 조로 나뉘어진다.
• 빈 조가 있을 수 없다.
• 조 별 인원수는 자유이다.
• 조 별로 티셔츠를 맞추고, 이 비용은 조에서 가장 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다.

# 입력
5 3
1 3 5 6 10

# 결과 
3

코드 설계하기

• 인접한 원생 간 비용을 계산해 우선 정렬하고,
• 이 값에 대해 가장 큰 비용이 나올 수 있는 원생 간의 Cost를 우선적으로 제외하고, 나머지를 더하면 된다.
  • 다시 검증하는 로직이 불필요하므로, Greedy Algorithm

구현 방법

1. 인접 원소 간 차이 계산
   정렬된 배열에서 인접한 원소 사이의 차이를 구한다.
   • 차이:
     • 3 - 1 = 2
     • 5 - 3 = 2
     • 6 - 5 = 1
     • 10 - 6 = 4
   • 결과: [2, 2, 1, 4]
2. 전체 범위(총 비용) 계산
   모든 원생을 하나의 그룹으로 묶으면 비용은 전체 범위가 된다.
   • 전체 범위 = max - min = 10 - 1 = 9
3. 정렬된 값 중 K - 1개의 gap 제거
   • K개의 그룹으로 분할하여 각 그룹 내의 비용(그룹 내 최대값과 최소값의 차이)을 최소화하기 위함이다.
   • 정렬된 배열에서 인접 원소 간의 차이들 중, 가장 큰 K - 1개의 gap을 제거하면, 배열은 K개의 연속된 구간(그룹)으로 분할된다.
   • K = 3 → 제거할 gap 개수 = 3 - 1 = 2
     • 차이 배열 [2, 2, 1, 4]에서 가장 큰 두 개의 gap는 4와 2이다.
4. 최소 비용 계산
   최종 최소 비용은 전체 값 범위에서 제거한 gap들의 합을 뺀 값이다.
   • 최소 비용=(전체 범위)−(제거한 K - 1개의 gap들의 합)
   • 계산:
     • 전체 범위: 9
     • 제거한 gap들의 합: 4 + 2 = 6
     • 최소 비용: 9 - 6 = 3

시간 복잡도

• 차에 대해 정렬을 수행하므로
  • O( (n - 1) log (n - 1)) = O(n log n)
  • 299,999×18.2≈5,460,000
  • 따라서 시간 내에 수행이 가능하다.

정답 코드 (Java)

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

public class Main {
    private static int N, K, answer;
    private static int[] arr;
    private static int[] subtract;
    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());
        }

        // 차이 배열 구하기
        subtract = new int[N - 1];
        for (int i = 0; i < N - 1; i++) {
            subtract[i] = arr[i + 1] - arr[i];
        }

        // 정렬
        Arrays.sort(subtract);

        answer = 0;

        // iteration 횟수 = (N - 1) - (K - 1)
        for (int i = 0; i < N - K; i++) {
            answer += subtract[i];
        }

        System.out.println(answer);
    }
}