[백준] 13164. 행복 유치원 - Python

[Gold V]

 

https://www.acmicpc.net/problem/13164

13164번: 행복 유치원

 

풀이

[백준] 2212. 센서 - Python 와 거의 동일한, 간단한 Greedy 문제.

 

모든 원생의 키를 오름차순으로 정렬 후, 옆 사람과의 키 차이를 저장하고,

키 차이를 다시 오름차순으로 정렬 후, 맨 뒤에서부터 (K-1)개를 빼고 모두 더하면 된다.

K개의 조로 나눈다는 것은, 중간에 키 차이를 무시하고 넘어갈 수 있는 횟수가 K-1번이라는 뜻이라고 생각할 수 있다.

 

AC.

N, K = map(int, input().split())

heights = list(map(int, input().split()))
heights.sort()  # 키 순 정렬

# 바로 옆 사람과의 키 차이를 계산하여 저장.
gaps = []
for i in range(len(heights)-1):
    gaps.append(heights[i + 1] - heights[i])
    
# 차이의 크기 순으로 정렬 후, 가장 큰 K-1개의 차이를 빼고 계산 (Greedy)
gaps.sort()
if K > 1:
    print(sum(gaps[:-(K-1)]))
else:
    print(sum(gaps))