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

13164번: 행복 유치원

 

문제

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

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

입력

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

출력

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

코드

from heapq import heappop, heappush

n, k = map(int, input().split())
height = list(map(int, input().split()))    # 오름차순 정렬된 원생들 키
# 인접한 원생끼리의 키 차이
diff = []
for i in range(1, n):
    heappush(diff, -(height[i]-height[i-1]))
# 경계선에 해당하는 값 제거
for _ in range(k-1):
    heappop(diff)

print(-sum(diff))

n명의 원생을 k개의 그룹으로 나눌 때 그룹의 경계는 k-1개이다.

이때 각 그룹의 티셔츠 만드는 비용은 그룹에 속한 팀원들끼리의 키 차이의 합이다. 이러면 그룹의 경계에 있는 원생끼리의 키 차이는 티셔츠 만드는 비용에 포함되지 않게 된다. 그러므로 티셔츠 만드는 비용을 최소로 하려면 키 차이값들 중 큰 값 k-1개를 빼고 남은 값들을 더하면 된다. 

문제의 예제를 보면서 설명해보면

아랫줄의 숫자들은 인접한 원생들끼리의 키 차이이다. 이 중에서 큰 값 3개를 골라서 빼면 아래와 같다.

차이값들 중 경계가 되는 값들만 티셔츠 만드는 값에서 빠지므로 티셔츠 제작비를 최소로 하려면 차이값들 중 큰 값 k-1개를 빼면 되는 것이다.