[백준/Python] 13164 행복 유치원

문제 링크

13164번: 행복 유치원

 

문제 풀이

• 각 조에서 가장 키가 작은 원생과 가장 키가 큰 원생의 차이만큼의 비용이 들게 되므로 이 차이를 최소화 해야 한다.
• 원생은 키 순으로 줄을 서 있으므로, 먼저 인접한 원생의 키 차이(arr[i+1]-arr[i])를 구한다. 이때 가장 차이가 많이 나는 원생은 같은 조가 되면 안되므로 다른 조로 분리를 해야 한다.
• 위의 과정을 k개의 조가 생성될 때까지 반복하고 각 조의 비용을 더한 값(sum(l[:n-k]))이 최솟값이 된다.

 

전체 코드

import sys

n, k = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))

l = []
for i in range(n-1):
    l.append(arr[i+1] - arr[i])

l.sort()
print(sum(l[:n-k]))