[Baekjoon] 13164번 : 행복 유치원

1. 문제

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

• 정렬 문제

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

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

// 입력
입력의 첫 줄에는 
유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과
나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 
공백으로 구분되어 주어진다. 
다음 줄에는 원생들의 키를 나타내는 N개의 자연수가 
공백으로 구분되어 줄 서 있는 순서대로 주어진다. 
태양이는 원생들을 키 순서대로 줄 세웠으므로, 
왼쪽에 있는 원생이 오른쪽에 있는 원생보다 크지 않다. 
원생의 키는 109를 넘지 않는 자연수이다.

// 출력
티셔츠 만드는 비용이 최소가 되도록 K개의 조로 나누었을 때, 
티셔츠 만드는 비용을 출력한다.

// 예제 입력 1 
5 3
1 3 5 6 10

// 예제 출력 1 
3

// 힌트
1조: 1, 3
2조: 5, 6
3조: 10

2. 핵심 아이디어

3. Python 문제풀이

import sys
input = sys.stdin.readline
read = lambda : input().rstrip()

n, k = map(int, read().split())
chil = list(map(int, read().split()))
costs = []

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

costs.sort()

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

4. Java 문제풀이