[BOJ13164 - Python] 행복 유치원

문제

---

13164번: 행복 유치원

 

행복 유치원에는 N명의 원생들이 있다. (1 ≤ N ≤ 300,000) - 30만명이 있는 유치원 ㄷㄷ

이들을 키에 대하여 오름차순으로 일렬로 세운 후 총 K개의 조로 나누려고 한다.

 

각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다.

조별로 인원수가 같을 필요는 없다.

 

이렇게 나눠진 조 각자 단체 티셔츠를 맞추려고 한다.

조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다.

 

K개의 조에 대해 티셔츠를 만드는 비용의 합의 최솟값을 구하는 것이 문제이다.

 

 

풀이

---

시간 제한이 1초이며, N의 범위가 300,000이다.

이 문제를 해결하려면 시간 복잡도가 O(NlogN) 미만이 되는 알고리즘을 설계해야 한다..!

 

원생들을 K개의 조로 나누는 것에 집중하는 것이 아닌, 인접하는 원생들 사이의 키 차이에 집중하여 문제에 접근하면 해결할 수 있다.

 

---

예시로 원생은 5명, 이들을 3개의 조로 나눠야 하며 각각의 키가 다음과 같이 주어진다고 해보자.

1 3 5 6 10

 

각 조에 대한 키 차이의 합이 가장 작도록 조를 편성하기 위해서는

인접하는 원생의 키 차이들 중 가장 큰 것부터 시작하여 그 사이를 갈라버려야 한다.

 

1. 가장 큰 키 차이 : 6과 10 사이

그 둘 사이를 갈라버린다.

 

2. 가장 큰 키 차이 : 1과 3 사이 / 3과 5 사이

둘 중 하나의 사이를 갈라버린다.

 

(1) 1과 3 사이를 갈라버릴 경우

(2) 3과 5 사이를 갈라버릴 경우

 

조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이는 조에서 인접한 원생의 키 차이들을 전부 더한 값과 같다.

따라서 답은 조로 갈라버리고 남은 인접하는 원생의 키 차이들의 합, 2 + 1 = 3이 된다.

 

 

정리해보자면, 원생들을 K개의 조로 나눠야 하는 경우

인접한 원생의 키 차이들 중 가장 큰 수 ~ K-1번째 가장 큰 수를 제외하고 나머지 키 차이들을 전부 더한 것이 답이다.

 

이걸 우째 혼자 생각하누?

 

 

코드

---

import sys

N, K = map(int, sys.stdin.readline().split())
h = list(map(int, sys.stdin.readline().split()))

d = []  # 키 차이
for i in range(N - 1):
    d.append((h[i + 1] - h[i]))
d.sort()

# 가장 큰 수 ~ K-1번째 가장 큰 수 제외, 키 차이들을 전부 더한 것과 같음
result = 0
for i in range(N - K):
    result += d[i]
print(result)

 

이와 똑같은 문제로는 BOJ2212 - 센서가 있다.

2212번: 센서

 

그리디 문제들.....

생각나는 풀이들은 너무 빡쎈데 정답 코드를 보면 으응..? 아이디어나 코드나 너무 간결해서 현타가 느껴진다.

쉬운 것부터 찬찬히 풀어보고, 풀이를 생각해내지 못해 정답을 찾아봤어도 그 내용들을 제대로 흡수해야겠다.