[알고리즘|파이썬] 백준 13164 행복 유치원

문제 링크: https://www.acmicpc.net/problem/13164

 

📌 문제 탐색하기

시간 제한: 1초
메모리 제한: 512 MB

 

✏️ 구해야 하는 정답

문제

원생의 수를 나타내는 자연수 N과 나누려고 하는 조의 개수를 나타내는 자연수 K

원생들의 키를 나타내는 N개의 자연수가 줄 서 있는 순서대로 주어지며 오름차순으로 주어짐.

각 조의 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다.

K개의 조에 대해 비용의 합 최소 값을 구하자.

 

조건

- 1 ≤ N ≤ 300,000

- 1 ≤ K ≤ N

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

 

---

📌 풀이하기 

예시 1.

N = 5

K = 3

원생의 키 = {1, 3, 5, 6, 10}

각 원생의 키와, 원생끼리의 키 차이를 나타내면 위와 같다.

이때 최소 비용을 생각해보면 원생끼리의 차이 값이 그 값이라는 것을 볼 수 있다.

K = 3이므로, 3개의 묶음을 만들어야하고, 이때 필요한 차이 값은 2개이다. 일반화 해보면 K-1개라고 생각해볼 수 있다.

차이가 {2, 2, 1, 4} 이고, 이 중에서 차이가 적은 합이 필요하다. 그러므로 차이 리스트에서 큰 값을 K-1개를 빼고 남은 값을 더하면 정답이 된다.

 

다른 예시로 동일한 로직을 적용해서 다시 살펴보자.

예시 2.

N = 10

K = 4

원생의 키 = {1, 2, 3, 5, 9, 10, 11, 12, 16, 17}

차이 값을 리스트로 만들어 보면 {1, 1, 2, 4, 1, 1, 1, 4, 1} 이 된다.

K=4이므로 K-1개를 뺀 값들로 K개의 묶음을 만들면 된다. 이때 빼야하는 K-1 개의 숫자는 차이 리스트에서 큰 K-1 개의 숫자이다.

{1, 1, 2, 4, 1, 1, 1, 4, 1} 중에서는 2, 4, 4 가 이중 큰 값 3개 이기 때문에 비용은 2, 4, 4 를 뺀 1 + 1 + 1 + 1 + 1 = 6이 된다.

 

---

📌 코드 설계하기

1. N, K, 원생 키 리스트 input을 받는다.

2. 원생 키의 차이를 구한 diff 리스트를 만든다.

3. diff 리스트를 오름차순으로 정렬한다.

4. diff 리스트에서 K-1개를 pop한다.

5. diff 리스트의 sum 값을 출력한다.

 

---

📌 정답 코드

n, k = map(int, input().split())
kids = list(map(int, input().split()))
diff = list()
for i in range(n-1):
    diff.append(kids[i+1]-kids[i])

diff.sort()
for _ in range(k-1):
    diff.pop()
print(sum(diff))