[python/파이썬] 백준 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

 

[문제 풀이]

 

n명의 원생을 k개의 조로 나누었을 때, 각 조의 제일 작은 원생과 제일 큰 원생 사이의 키차이가 작아지도록 해야 한다.

처음에는 k개의 조로 나누는 경우의 수가 굉장히 많기 때문에 어떤 방식으로 하면 좋을지 고민이 많았다.

하지만 이 문제는 어떻게 나누느냐에 집중하면 풀기가 어렵다.

 

일단 바로 옆에 위치한 원생들 간의 키 차이를 구해서 diff 리스트에 저장한다.

 

kids = [1, 3, 5, 6, 10] 

 

키가 이렇게 주어졌다면

 

diff = [3-1, 5-3, 6-5, 10-6] = [2, 2, 1, 4]

 

만약에 3개의 조로 나눈다고 했을 때

최소가 되는 값은

1,3 / 5, 6/ 10

이렇게 나누게 된다 

이때 비용은 diff [0] + diff [2]가 된다.

4개의 키 차이 중에서 2개의 키차이 값만 더하게 된다.

 

최소가 아니더라도 다른 구성으로 조를 나눠 보면

1, 3, 5/ 6/ 10

이렇게 나누면

비용은 diff [0] + diff [1] 이 된다.

 

5명을 3개의 조로 나눌 때 2개의 diff값을 더해줬으므로

일반화하면 

n-k개의 diff값을 더해주면 된다.

 

최소가 되어야 하기 때문에

diff값을 오름차순으로 정렬 후에 작은 값부터 해서 n-k개 더해주면 최소 비용이 나온다.

 

[소스 코드]

import sys

input = sys.stdin.readline

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

kids = list(map(int, input().split()))
diff = [] #인접한 원생과의 키차이를 저장
for i in range(0,n-1):
    diff.append(kids[i+1]-kids[i]) #i번째 원생과 i+1번째 원생 사이의 키차이
    
diff.sort() #키차이를 오름차순으로 정렬
sum = 0
for i in range(n-k): #n-k개의 키차이를 더함
    sum += diff[i]
    
print(sum)