[Python 알고리즘] 백준 13164번 : 행복한 유치원

문제

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

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

 

입력

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

 

출력

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

 

예제 입력

5 3
1 3 5 6 10

 

예제 출력

3

 

내가 제출한 풀이

import sys

n, k = list(map(int, sys.stdin.readline().strip().split()))
childrens = list(map(int, sys.stdin.readline().strip().split()))
diff = []
result = 0

for i in range(n - 1):
    diff.append(childrens[i + 1] - childrens[i])

diff.sort()

for i in range(n - k):
    result += diff[i]

print(result)

 

 

문제 해설

문제에서 봐야할 관점은 다음과 같다.

1. 각 조에는 원생이 적어도 한 명 이상이어야 한다.

2. 같은 조에 속한 원생들은 서로 인접해 있어야 한다.

3. 입력된 원생들은 키 순서대로 줄을 세웠다.

 

# [2, 2, 1, 4]
for i in range(n - 1):
    diff.append(childrens[i + 1] - childrens[i])

2번(같은 조에 속한 원생들은 서로 인접해 있어야 한다) 규칙을 통해 알 수 있듯이 i(현재 원생)는 i-1과 i+1로만 조를 짝지을 수 있다. 그렇기 때문에 각각의 원생들의 차이를 구해줘야 한다.

 

# [1, 2, 2, 4]
diff.sort()

for i in range(n - k):
    result += diff[i]

N - K를 해준 이유는 차이 값이 큰 원생들과 조를 이루게되면 최솟값을 절대 구할 수 없기 때문이다. 그래서 혼자 조를 이루는 최댓값 N개만 제외한 최소비용으로 조를 이루는 것이다.