[백준] #13164 행복 유치원 (python)

13164번: 행복 유치원 (acmicpc.net)

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

 

# Code

import sys
input = sys.stdin.readline

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

array = []
for i in range(1, n):
    array.append(kids[i] - kids[i-1])

array.sort(reverse=True)
print(sum(array[k-1:]))

# Comment

아.. 어렵다.. 풀이를 참고해도 이해가 잘 안돼서... 돌아댕기다가 그나마 이해를 한 풀이를 참고했다.

인접한 애들끼리 그룹을 지어야하니까, 인접한 유치원생들의 키 차이를 각각 구한다. n명 중 k개의 그룹을 만든다고 했으므로, 경계는 k-1일 것이다. 키 차이 값이 큰 순서대로 k-1개를 빼고 나머지를 더해주면 티셔츠 비용의 최솟값이 나온다. 

ex)

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

=> 키 차이를 내림차순 정렬
5 3 2 2 1 1 1
여기서 값이 큰 것 k-1개, 즉 3개를 빼주면 5 3 2가 제거된다.
따라서 인덱스가 3인 값부터 끝까지 sum을 구해주면 2+1+1+1=5 -> 티셔츠의 최소 비용

이렇게 이해했는데, 맞게 이해한건지 모르겠다... 좀 어렵다. ㅠ.ㅠ