[백준/파이썬] 13164번 행복 유치원

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

13164번: 행복 유치원

문제 해석

 

유치원생들이 내림차순의 키 순서대로 주어진다. 유치원들은 1명 이상으로 조를 구성할 수 있을 때 k개 이하의 조를 구성할 때,

해당 조원의 키차이만큼 티셔츠를 맞추는 비용이 소모된다. 비용이 최소가 되는 값을 구하는 문제이다.

---

코드

 

input = __import__('sys').stdin.readline

n, k = map(int, input().split())
arr = list(map(int, input().split()))

# 원생들의 키 차이를 나타내는 배열
cost = []
for i in range(1, len(arr)):
    cost.append(arr[i] - arr[i - 1])
    
# 한 조를 줄일 때 마다 가장 최소 비용을 더해주면 됨. 즉 n - k만큼 더하면 k조가 되는 최소 비용
cost.sort()
ans = 0
for i in range(n - k):
    c = cost[i]
    ans += c
print(ans)

---

문제 풀이

 

먼저 조를 나눌때를 생각해보자.

1 3 5 6 10의 유치원생이 존재할 때 3개의 조로 나누어보자. 현재 조의 수는 5이다.

(1, 3) (5, 6) (10) 해당 방법으로 나누나 (1, 3, 5) (6) (10) 해당 방법으로 나누나 2명의 유치원생을 묶으면 조가 1개씩 줄어든다.

즉 조를 나누기 위해서는 n - k번만큼 나누어주면 된다.

 

다음은 조를 묶는 2명의 유치원생을 고르면된다. 이때는 항상 가장 최선의 수를 선택할 수 있는 그리디 알고리즘으로 선택해 나갈 수 있다.

먼저 입력된 유치원생에 서로의 키차이를 저장하고 해당 키차이를 내림차순 정렬하면 된다.

 

마지막으로 n - k 만큼 선택해 조를 묶으면 k개의 조를 나누고, 그 최소 비용을 구할 수 있다.