백준_13164_파이썬_쉬운풀이(행복 유치원)

※ 첫 접근

 모든 경우의 수를 알아야하는데 문제 입력 부분을 봤을 때 n이 최대 삼십만개인 것을 보고 완전 탐색은 아니겠구나 생각했다. 이분 탐색을 떠올렸지만 정렬된 구간은 있지만 mid를 재설정 하는 과정에서 시간초과가 나서 패스했다. 다음으로 그리디 알고리즘을 떠올렸다. 그리디 알고리즘으로 반복 한 번에 풀어야만 시간초과가 나지 않을 것만 같았다.

 

※ 풀이

모든 유치원생이 혼자 있어야만 최소 비용일 수 있다. 1 ㅣ 3 ㅣ 5 ㅣ 6 ㅣ10 일 때 최소가 된다 n-1개의 막대기가 존재한다. 여기서 저 사이의 막대기를 치우면 한 조에 두명이상이 되고 차이만큼 비용이 증가하기 시작한다.  각 차이는 (2,2,1,4)이다. 여기서 우리는 k개의 조로 나누어야 하기에 k-1개의 막대기가 남아있어야 한다. 그렇다면 나머지 막대기는 치워야하는데 몇개를 치워야 할까? 식을 세워보자면 n-1 - x = k-1 저 식을 계산해보면 x = n-k개가 된다. 즉 n-k개만큼 막대기를 치워야 한다. 그럼 각 차이를 오름차순으로 정렬한 다음 n-k개의 합을 더해주면 된다.

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

data = list(map(int,input().split()))

dif = [0] * (len(data) - 1)

for i in range(len(data)-1):
    dif[i] = data[i+1] - data[i]

dif.sort()
total = 0
total = sum(dif[:n-k])
print(total)

 

※ 회고

처음에는 도대체 저 많은 경우를 다 알아야 하는데 그리디겠지 싶었으나 이게 왜 그리디인가 싶었다. 일단 그리디니 각 차이를 구하는데 까지는 구상했지만 여기서 어떻게 더 나아가야 하는지 생각을 하지 못했다. 막대기? 뭔가 입체적으로 생각했어야 했나? 쉽지 않은 문제였다.