문제 링크
문제 풀이
- 각 조에서 가장 키가 작은 원생과 가장 키가 큰 원생의 차이만큼의 비용이 들게 되므로 이 차이를 최소화 해야 한다.
- 원생은 키 순으로 줄을 서 있으므로, 먼저 인접한 원생의 키 차이(arr[i+1]-arr[i])를 구한다. 이때 가장 차이가 많이 나는 원생은 같은 조가 되면 안되므로 다른 조로 분리를 해야 한다.
- 위의 과정을 k개의 조가 생성될 때까지 반복하고 각 조의 비용을 더한 값(sum(l[:n-k]))이 최솟값이 된다.
전체 코드
import sys
n, k = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
l = []
for i in range(n-1):
l.append(arr[i+1] - arr[i])
l.sort()
print(sum(l[:n-k]))
반응형
'Coding Test > BOJ' 카테고리의 다른 글
[백준/Python] 16564 히오스 프로게이머 (0) | 2024.02.24 |
---|---|
[백준/Python] 2589 보물섬 (0) | 2024.02.23 |
[백준/Python] 12865 평범한 배낭 (0) | 2024.02.20 |
[백준/Python] 2564 경비원 (0) | 2024.02.19 |
[백준/Python] 2343 기타 레슨 (2) | 2024.02.17 |