[백준 13164번] 파이썬 - 행복 유치원

백준 13164 - 행복 유치원

시간 제한 1초, 메모리 제한 512MB

# 조건

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

입력

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

출력

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

# 접근 방법

• 우선 N과 K가 같다면 0을 출력해준다.
• 원생의 수가 300,000명이므로 모든 경우의 수를 탐색해줄 수는 없다.
• 티셔츠를 맞추는 비용은 가장 큰 사람과 작은 사람의 차이만큼 발생하고, 같은 조의 원생들은 서로 인접해 있어야 한다.
• 따라서 인접한 원생끼리의 키 차이를 미리 구해준다.
  • 구해준 키 차이를 내림차순으로 정렬 한 후
  • k-1개 만큼 제외한 후 합을 구해주면 된다.
  • 가장 큰 키 차이를 제외하고 그룹을 구성하는게 최소값이 보장되기 때문이다.
• k-1개 만큼 빼는 이유는 7명을 3그룹으로 나눈다고 가정하자
  • 3 10 12 13 17 20 21의 차이가 난다면
  • 7 2 1 4 3 1 의 키 차이 배열이 주어지고
  • 가장 차이가 많이 나는 7과 4의 위치로 나눠주는 것인데 이 때 갈라주는 횟수는 k-1번만큼 갈라주어야 k개의 그룹이 나오기 때문이다.
  • 3 / 10 12 13 / 17 20 21 의 그룹이 최소의 비용을 가져온다.

import sys  
input = sys.stdin.readline  

N, K = map(int, input().split())  
children = [*map(int, input().split())]  
pre = [children[i] - children[i-1] for i in range(1, N)]  
pre.sort(reverse=True)  
print(sum(pre[K-1:]))