13164번 행복 유치원

문제

https://www.acmicpc.net/problem/13164
행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다.

이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자.

풀이

인접한 원생들끼리 그룹을 지어야하므로 인접한 원생들의 키 차이를 배열에 넣는다.

n명 중 k개의 그룹으로 나눈다고 했을 때, 그 경계(무시할 수 있는 키 차이)는 k-1개이고 반드시 넣어야할 키 차이의 개수는 n-k개이다.

키 차이를 넣은 배열이 오름차순이라면 n-k개 까지만 더해서 뒤에 k-1개의 큰 숫자들을 잘라내고, 배열이 내림차순이라면 앞에 k-1개를 잘라낸다.

그 후 남은 비용들 모두 더해서 출력하면 된다.

ex)

7명 중 3개의 그룹을 만든다고 할 때,
1 3 5 6 10 11 16 -> 오름차순으로 입력된 아이들의 키
2 2 1 4 1 5 -> 인접한 아이들 간의 키 차이

키 차이를 오름차순 정렬

1 1 2 2 4 5
인덱스 n-k(4) 이전 까지만 더하면, 뒤에서 k-1(2)개 4 5가 제거된다.
그 후 sum을 구해주면 1+1+2+2 = 6 -> 최소 비용

키 차이를 내림차순 정렬

5 4 2 2 1 1
인덱스 k-1(2)부터 끝까지 더하면, 앞에 k-1(2)개 5 4가 제거된다.
그 후 sum을 구해주면 2+2+1+1 = 6 -> 최소 비용

전체 코드

import sys
input = sys.stdin.readline

n, k = map(int,input().split())
l = list(map(int,input().split()))
costs = []

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

print(sum(costs[:n-k]))