[백준] 13164 행복 유치원

문제

• N명의 원생들을 키 순서로 세우고 K개의 조로 나누려고 한다. 
• 각 조는 적어도 1명 이상이 있어야 하고, 같은 조에 속한 원생은 서로 인접해야 한다.
• 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다고 할 때, 최소 비용 구하기

 

• 1 <= K <= N <= 300,000

 

풀이

• N명을 K개의 조로 나눠야 하고, 각 조에서 티셔츠를 만드는 비용(가장 키 큰 사람 - 가장 키 작은 사람)의 합의 최소를 구해야 한다.
• 최소 비용은 각 조에 1명의 원생이 있는 경우로 0원이다.
  -> 키 차이가 크게 나는 경우 해당 원생 한 명을 하나의 조로 나누자.
• K-1명의 키 큰 사람을 하나의 조라고 생각하고, 나머지를 N-K까지의 키차이를 더하면 티셔츠를 만드는 비용이 된다.

 

# 입력 받기
N, K = map(int, input().split())
heights = list(map(int, input().split()))

# 키 차이 구하기
sub = [heights[i+1]-heights[i] for i in range(N-1)]
sub.sort()

# 최소 비용 구하기
answer = 0
for i in range(N-K) :
    answer += sub[i]

print(answer)

 

References

• 백준 그리디