[파이썬/Python] 백준 13164번: 행복 유치원

숨·2024년 8월 24일

코테

알고리즘 문제 풀이

목록 보기

60/105

📌 문제 : 백준 13164번

📌 문제 탐색하기

N : 원생의 수 $(1 ≤ N ≤ 300,000)$
K : 조의 개수 $(1 ≤ K ≤ N)$
heights : 원생의 키 $(1 ≤ heights ≤ 10^9)$

N명의 원생을 K개의 조로 나누고,조에서 가장 큰 원생의 키에서 가장 작은 원생의 키를 뺀만큼 티셔츠 비용이 들 때,
티셔츠 만드는 최소 비용을 구하는 문제이다.

문제 풀이

⭐️ 조를 나눌 때 고려해야 할 점

각 조에 원생이 적어도 한 명 이상, 조별로 인원수 같지 않아도 됨

같은 조 원생은 서로 인접

각 원생의 키는 키 기준으로 오름차순 입력

비용 = 가장 큰 키 - 가장 작은 키이므로 키 차이를 최소화해서 조를 나눠야 한다.

같은 조 원생은 서로 인접해있다고 했기 때문에 입력받은 키 리스트에서 각 요소들 사이의 차이를 계산한다.
그 후, 많은 차이가 나는 구간을 피해서 K개 조를 만들면 될 것이다.

✏️ 예제 1로 확인해보자.
5명의 원생으로 3개의 조를 만들어야 하고, 각 원생의 키는 다음과 같다.

원생	0	1	2	3	4
키	1	3	5	6	10

원생 사이의 키 차이를 계산해보면 다음과 같다.

원생	0, 1	1, 2	2, 3	3, 4
차이	2	2	1	4

3개의 조를 만들어야 하고, 이때 각 조 사이엔 아래와 같이 2개의 분리가 필요하다.
1, 3 | 5, 6 | 10

따라서 계산한 차이 중 가장 큰 차이를 보이는 2가지를 선택해서 제외한 나머지의 차이 합을 구한다면 원하는 최소의 비용을 얻을 수 있을 것이다.

원하는 조의 개수 K가 있을 때 각 조는 K-1의 분리를 가지게 된다.
→ 키 차이를 오름차순 정렬해 그 차이 중 K-1개를 제외한 나머지 키 차이를 계산하면 된다!

가능한 시간복잡도

키 차이 계산 → $O(N)$
키 차이 오름차순 정렬 → $O(NlogN)$
합 계산 → $O(N)$

최종 시간복잡도
$O(NlogN)$ 로 최악의 경우 $O(3*10^5*log(3*10^5))$ 이 된다.
이는 1초내에 연산 가능하다.

알고리즘 선택

각 키의 차이를 오름차순 정렬하고 원하는 값까지 합 계산

📌 코드 설계하기

N, K 입력
키 입력
각 키 차이 계산
차이 정렬
끝에서 K-1개 제외
차이 합 계산

📌 시도 회차 수정 사항

1회차

# 끝에서 K-1개 제외
d = d[:K-1]

각 키 차이를 정렬하고 K-1개를 제외하는 코드에서 슬라이싱을 잘못 수행했다.
차이의 개수는 N-1개이고 여기서 K-1개를 제외해야 하므로 $(N - 1) - (K - 1) = N - K$ 까지 슬라이싱 하도록 수정했다.

📌 정답 코드

import sys

input = sys.stdin.readline

# N, K 입력
N, K = map(int, input().split())

# 키 입력
heights = list(map(int, input().split()))

# 각 키의 차이 계산
d = []
for i in range(1, N):
    d.append(heights[i] - heights[i-1])

# 차이 정렬
d.sort()

# 끝에서 K-1개 제외
d = d[:N - K]

# 차이 합 계산
print(sum(d))