[알고리즘 일기 - 파이썬] 196. 행복 유치원

문제 196. (2022-02-26)

 

13164번: 행복 유치원

Baekjoon 13164. 행복 유치원

[파이썬(python) - Greedy]

행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다.

이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자.

 

---

입력

입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들의 키를 나타내는 N개의 자연수가 공백으로 구분되어 줄 서 있는 순서대로 주어진다. 태양이는 원생들을 키 순서대로 줄 세웠으므로, 왼쪽에 있는 원생이 오른쪽에 있는 원생보다 크지 않다. 원생의 키는 109를 넘지 않는 자연수이다.

 

---

출력

티셔츠 만드는 비용이 최소가 되도록 K개의 조로 나누었을 때, 티셔츠 만드는 비용을 출력한다.

 

---

입력 예시

5 3
1 3 5 6 10

 

---

출력 예시

3

 

---

TRY1 시간초과

from sys import stdin

n, k = map(int, stdin.readline().split())
kids = list(map(int, stdin.readline().split()))
com = []
while len(kids) > 1:
    minimum = [0, 1, kids[1] - kids[0]]
    for i in range(2, len(kids)):
        if minimum[2] > (kids[i] - kids[i - 1]):
            minimum = [i - 1, i, (kids[i] - kids[i - 1])]
    kids.pop(minimum[1])
    kids.pop(minimum[0])
    com.append(minimum[2])

if n // 2 < k:  # 혼자서 조하는 경우 '0'이므로 가장 최적의 경우이다.
    k -= 1

print(sum(com[:k]))

• minimum 리스트에 가장 차이가 작은 원소들을 첫번째, 두번째 인덱스에 저장한다.
• 세번째 인덱스에는 두 원소의 차를 저장한다.
• ${O(n^2)}$ 시간 복잡도 발생 -> 시간 초과

 

❧ 정답

 

🔎IDEA) Greedy - 학생 키의 차를 바로 리스트에 저장한다.

[Line 6 - 7]
👉 학생들 키의 차를 바로 계산해서 com 리스트에 저장한다.
👉 이후 오름차순으로 정렬하고 k개의 조를 만들어야하므로 n-k 만큼의 학생키의 차를 더한다.