[백준 13164번] 행복 유치원 문제 풀이

 

< 문제  >

 

 

 

< 입출력 >

 

 

< 풀이 >

k개의 그룹을 만들기 위해서는 k-1 개의 구분이 필요하다. 

연속하는 숫자의 차이를 계산한다.

위의 경우, 3개의 구분이 필요하다. 차이가 큰 3개를 없애주는 것이 차이를 가장 줄일 수 있는 방법이다.

예시에서는 2, 4, 4 차이가 있는 부분에 구분을 두는 것이 가장 차이의 합이 작아진다.

1번과 2번의 경우 같은 2, 4, 4를 줄이기 때문에 결과값은 같다.

 

 

 

 

 

< 구현 코드 >

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
height = list(map(int, input().split()))
height.sort()
diff = []  # 연속하는 수의 차이를 담을 배열

for i in range(0, N-1):
    diff.append(height[i+1]-height[i])

diff.sort()

print(sum(diff[:len(diff)-K+1]))   # 총 차이의 개수를 구해서 가장 큰 K-1개를 제외하고 더해준다