[JAVA] 백준 13164_행복 유치원

[문제링크]

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

 

📌 문제 탐색하기

이 문제는 원생들을 K개의 조로 나누는 문제로, 목표는 각 조의 티셔츠 비용의 합을 최소화 하는것이 목적이다. 각 조의 티셔츠 비용은 그 조에서 가장 큰 키와 가장 작은 키의 차이로 계산 됨. 원생들은 이미 키 순서대로 주어지므로, 각 조의 티셔츠 비용은 해당 조의 첫 번째 원생과 마지막 원생의 키 차이이다. K개의 조로 나누려면, 최소한 한 명씩 원생이 포함되어야 하므로, 한 조에는 최소 한 명 이상의 원생이 있어함.

📌 코드 설계하기

 

• 입력 처리: 원생들의 키를 입력받고, heights 배열에 저장합니다.
• 차이 계산: 원생들 간의 키 차이를 계산하여 diffs 리스트에 저장합니다.
• 차이 내림차순 정렬: diffs 리스트를 내림차순으로 정렬하여 가장 큰 차이를 앞쪽으로 배치합니다.
• 최소 비용 계산: 전체 차이들의 합에서 가장 큰 K-1개의 차이를 빼면, 나머지 차이들의 합이 최소 비용이 됩니다.

 

📌 가능한 시간복잡도 

차이 계산은 O(N) , 정렬은 O(N log N)으로 최종적으로 생각하는 가능한 시간복잡도는 O(N log N)입니다.

📌 정답 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        
        int[] heights = new int[N];
        for (int i = 0; i < N; i++) {
            heights[i] = sc.nextInt();
        }
        
        // 원생들 간의 차이를 저장할 리스트
        List<Integer> diffs = new ArrayList<>();
        
        // 원생들 간의 차이를 계산하여 diffs에 저장
        for (int i = 0; i < N - 1; i++) {
            diffs.add(heights[i + 1] - heights[i]);
        }
        // 차이들을 내림차순으로 정렬
        Collections.sort(diffs, Collections.reverseOrder());
        
        // 비용을 계산: 전체 비용에서 가장 큰 K-1개의 차이를 뺀다
        int cost = 0;
        for (int i = 0; i < N - 1; i++) {
            cost += diffs.get(i);
        }
        // 가장 큰 K-1개의 차이를 빼면 나머지 비용이 최소 비용이 된다
        for (int i = 0; i < K - 1; i++) {
            cost -= diffs.get(i);
        }
        System.out.println(cost);
    }
}