[baekjoon] 백준 13164번(파이썬): 행복 유치원

문제

13164번: 행복 유치원

- 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다.

- 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다.

- 조별로 인원수가 같을 필요는 없다.

- 이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다.

- 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다.

- 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다.

- 태양이를 도와 최소의 비용을 구하자.

- 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다.

- 키를 나타내는 N개의 자연수가 공백으로 구분되어 줄 서 있는 순서대로 주어진다.

- 태양이는 원생들을 키 순서대로 줄 세웠으므로, 왼쪽에 있는 원생이 오른쪽에 있는 원생보다 크지 않다. 

- 원생의 키는 10^9를 넘지 않는 자연수이다.

알고리즘

- 원생의 수와 조의 개수를 입력받는다.

- 원생의 키를 입력받는다.

- 원생 각각의 키 차이를 반복문을 통해 구한다.

-  키 차이를 오름차순으로 정렬하여 최소 키 차이부터 계산하기 쉽게 만든다.

- 학생의 수에서 조를 뺀 수만큼 원생의 키 차이 수를 반복하여 최소 비용을 구한다.

코드

import sys

n, k = map(int, sys.stdin.readline().split())
Length = list(map(int, sys.stdin.readline().split()))
res = []

# 원생 각각의 키 차이를 구한다.
for i in range(0, n - 1):
    res.append(Length[i+1] - Length[i])

# 키 차이를 오름차순으로 정렬한다.
res.sort()
result = 0

# 학생의 수에서 조를 뺀 수만큼 원생의 키 차이 수를 반복하여 최소 비용을 구한다.
for i in range(n - k):
    result += res[i]

print(result)

github

junjange/CodingTest