[BOJ/13164] 행복 유치원 (그리디)

# 13164 행복 유치원 문제

 

행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다.
이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자.

 

문제를 풀게 된 내 흐름을 설명해보겠다.

문제를 먼저 봤을때 제일 먼저 적었던 것은

전체 N명 / 키 순서 => 오름차순 / k개 조 / 가격 : 제일큰 - 제일 작은

이 키워드들로 시작했다.

 

제일 처음 문제를 볼 때는 완전탐색 / 백트래킹 이렇게 두가지 방법이 생각났다.

 

제일 첫 관문은 N명을 어떻게 k개로 나눌지에 대한 방법이었다.

여기서 생각난 건 백트래킹이었다.

1-n까지의 숫자를 k번 뽑아서 합이 n이 되게끔 만드는 로직을 작성하였다.

그 후, 백트래킹으로 5를 k개로 나눌 수 있는 조합을 찾고, 오름차순 정렬을 한 원생들을 나누는 방법!으로 구현하려고 마음먹었다.

 

두번째는 조합으로 나눈 원생들의 가격을 어떻게 측정할 것이냐 였다.

그 조합으로 돌아가면서 가격을 측정해서 결과적으로 최소를 구하는 방법을 채택!

 

두가지 생각을 마친 나는 아래와 같은 코드를 작성했다.

n, k = tuple(map(int, input().split()))
arr = []
cnt = 0
kids = sorted(list(map(int, input().split())))
ans = max(kids)


def choose_number(curr_num):
    global cnt, ans
    if (curr_num == k and cnt == n):
        temp = 0
        temp_ans = 0
        for elem in arr:
            temp_ans += kids[elem+temp-1] - kids[temp]
            temp += elem
        ans = min(ans, temp_ans)

    for i in range(1, n):
        if (cnt+i > n):
            return
        arr.append(i)
        cnt += i
        choose_number(curr_num+1)
        cnt -= i
        arr.pop()


choose_number(0)
print(ans)

 

그 결과..

두둥

런타임에러 등장...

띠로리로

여기서부터 뭔가 크게 잘못됨을 감지..

 

잘못돼도 한참 잘못됐다.

일단 아이디어가 어느정도 필요했다.

k개의 조로 나누기 위해서는 N을 k-1개의 기준으로 잘라야한다.

그 기준은 옆에있는 수와의 차이이다.

수차이가 큰 기준으로 나눠야 그 값이 가격으로 측정되지 않을거기 때문에 가장 큰 차이를 가지고 있는 k-1개를 

 

예를 들어,

n=7 k=3

1 3 4 8 11 15 20 이라고 해보자

>2 1 4 3 4 5

이 차이를 오름차순 하면 => 1 2 3 4 4 5이다.

1 2 3 4 /4/ 5 -> 4와 5가 기준으로 조가 나뉘어져야 비용의 합이 최소가 된다.

여기서 높은 순서대로 k-1개를 제거한 후의 합이 답이다.

 

위 로직을 반영한 코드가 아래의 코드이다.

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
kids = list(map(int, input().split()))

ans = []
for i in range(1, n):
    ans.append(kids[i] - kids[i-1])
ans.sort(reverse=True)

print(sum(ans[k-1:]))

 

기준점을 생각하는 마인드를 갖자