[백준/Python] 13164 행복 유치원

 

📌문제 탐색하기

• N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개 조로 나누고자 함
• 각 조에는 원생이 적어도 한명, 같은 조에 속한 원생들은 서로 인접해있어야 함
• 조마다 각자 단체 티셔츠를 만들 때, (조에서 가장 키가 큰 원생의 키 - 가장 키가 작은 원생의 키) 만큼의 비용
• K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 했을 때, 최소 비용 구하기

편성해야 할 조가 K개 남아 있을 때, N명의 키 순으로 줄 세워진 원생들 중 조를 최적으로 편성하는 방법은 인접한 원생들 사이의 키 차이를 계산하여, 그 차이값 중 가장 큰 값을 기준으로 K−1개의 구간을 나누는 것이다.

1. N명의 원생들의 키를 오름차순으로 정렬한다. (문제에서 이미 정렬된 상태로 주어짐)
2. 인접한 원생들 간의 키 차이를 계산하여 배열에 저장한다.
   예를 들어, 원생의 키가 [1, 3, 5, 6, 10]이라면 각 차이는 [2, 2, 1, 4]가 된다.
3. 이 차이 배열에서 K−1개의 가장 큰 차이를 선택한다. 이 K−1개의 차이가 조를 나누는 기준이 된다.
4. 전체 키 차이의 합에서 선택한 K−1의 차이를 제외한 나머지 합이 티셔츠 제작 비용의 최소 합이 된다.

---

📌코드 설계하기

1. N명의 원생의 키와 편성해야 할 조의 개수 K를 입력받는다.
2. 원생들의 키를 오름차순으로 정렬하여 리스트 heights로 저장한다.
3. 인접한 원생들 간의 키 차이를 계산하여 리스트 differences에 저장한다.
4. differences 리스트를 내림차순 정렬한다.
5. differences[K-1:]의 모든 원소의 합을 계산하여 출력한다.

 

---

📌정답 코드

N, K = map(int, input().split())
heights = list(map(int, input().split()))
differences = sorted([heights[i+1]-heights[i] for i in range(N-1)], reverse=True)

print(sum(differences[K-1:]))