백준 13164 - 행복 유치원 (파이썬)
글 작성자: pental
https://www.acmicpc.net/problem/13164
풀이
- N명의 원생이 있고, 키가 오름차순으로 주어진다.
- 이 원생들을 K개의 조로 나누려고 한다.
- 각 조에서 가장 키가 큰 원생과 작은 원생의 차이가 해당 조의 비용
- 전체 비용의 합을 최소화 하는것이 문제 풀이의 요점
그리디 알고리즘을 이용해서 해결할 수 있다.
- 키 차이 계산
- 원생들은 이미 정렬되어 있다.
- 연속한 원생들끼리의 키 차이를 구한다.
- D[i] = A[i + 1] - A[i] (N - 1개의 차이 값)
- 큰 차이부터 제거
- 처음 모든 원생을 하나의 그룹으로 묶었을 때, 비용은 전체 키 범위인 A[N - 1] - A[0] 이다.
- 조를 K개로 나누려면, K - 1번 끊어야한다.
- 따라서 키 차이 배열 D에서 가장 큰 값부터 (K - 1)개를 제거하면 비용이 최소화된다.
- 그리디 알고리즘
- 키 차일 배열 D를 내림차순 정렬한 후, 상위 K - 1개의 값을 빼면 최소 비용이 된다.
시간 복잡도 분석
- 키 차이 계산: O(N)
- 정렬: O(N \log N)
- 최댓값 K-1개 선택: O(K)
- 총 시간 복잡도: O(N log N) (정렬이 주된 비용)
코드
# 백준 13164 - 행복 유치원
# 분류 : 그리디
N, K = map(int, input().split())
A = list(map(int, input().split()))
D = [A[i + 1] - A[i] for i in range(N - 1)]
D.sort(reverse=True)
answer = A[N - 1] - A[0]
for i in range(K - 1) :
answer -= D[i]
print(answer)
'Programming > 백준' 카테고리의 다른 글
백준 16439 - 치킨치킨치킨 (0) | 2025.03.11 |
---|---|
백준 17255 - N으로 만들기 (파이썬) (0) | 2025.03.10 |
백준 17951 - 흩날리는 시험지 속에서 내 평점이 느껴진거야 (파이썬) (0) | 2025.03.09 |
백준 2503 - 숫자 야구 (파이썬) (1) | 2025.03.09 |
백준 17944 - 퐁당퐁당 1 (파이썬) (0) | 2025.03.08 |
댓글
이 글 공유하기
다른 글
-
백준 16439 - 치킨치킨치킨
백준 16439 - 치킨치킨치킨
2025.03.11 -
백준 17255 - N으로 만들기 (파이썬)
백준 17255 - N으로 만들기 (파이썬)
2025.03.10 -
백준 17951 - 흩날리는 시험지 속에서 내 평점이 느껴진거야 (파이썬)
백준 17951 - 흩날리는 시험지 속에서 내 평점이 느껴진거야 (파이썬)
2025.03.09 -
백준 2503 - 숫자 야구 (파이썬)
백준 2503 - 숫자 야구 (파이썬)
2025.03.09