백준 13164 - 행복 유치원 (파이썬)

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

풀이

1. N명의 원생이 있고, 키가 오름차순으로 주어진다.
2. 이 원생들을 K개의 조로 나누려고 한다.
3. 각 조에서 가장 키가 큰 원생과 작은 원생의 차이가 해당 조의 비용
4. 전체 비용의 합을 최소화 하는것이 문제 풀이의 요점

그리디 알고리즘을 이용해서 해결할 수 있다.

1. 키 차이 계산
   1. 원생들은 이미 정렬되어 있다.
   2. 연속한 원생들끼리의 키 차이를 구한다.
   3. D[i] = A[i + 1] - A[i] (N - 1개의 차이 값)
2. 큰 차이부터 제거
   1. 처음 모든 원생을 하나의 그룹으로 묶었을 때, 비용은 전체 키 범위인 A[N - 1] - A[0] 이다.
   2. 조를 K개로 나누려면, K - 1번 끊어야한다.
   3. 따라서 키 차이 배열 D에서 가장 큰 값부터 (K - 1)개를 제거하면 비용이 최소화된다.
3. 그리디 알고리즘
   1. 키 차일 배열 D를 내림차순 정렬한 후, 상위 K - 1개의 값을 빼면 최소 비용이 된다.

시간 복잡도 분석

1. 키 차이 계산: O(N)
2. 정렬: O(N \log N)
3. 최댓값 K-1개 선택: O(K)
4. 총 시간 복잡도: O(N log N) (정렬이 주된 비용)

코드

# 백준 13164 - 행복 유치원
# 분류 : 그리디

N, K = map(int, input().split())
A = list(map(int, input().split()))
D = [A[i + 1] - A[i] for i in range(N - 1)]
D.sort(reverse=True)

answer = A[N - 1] - A[0]
for i in range(K - 1) :
    answer -= D[i]

print(answer)