[알고리즘][Python] 백준 13164 행복 유치원 문제 풀이

문제 출처 : www.acmicpc.net/problem/13164

13164번: 행복 유치원

---

문제 해석 : 그룹을 만들어 그룹내에 키차이가 최소가 되도록 모든 그룹의 키 차이를 구하는 문제이다.

 

문제 풀이 : N명의 학생들을 K개의 그룹으로 나눈다고 했을 때 달리 말하면 N-K 개의 키 차이를 무시할 수 있다는 것이다. 이러한 원리에 따라서 알고리즘을 작성하면 풀 수 있다.

---

풀이 코드

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

diff = []
for i in range(N-1):
    diff.append(person[i+1] - person[i])
diff.sort()

answer = 0
for i in range(N-K):
    answer += diff[i]
print(answer)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.