문제
행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다.
이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자.
입력
입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들의 키를 나타내는 N개의 자연수가 공백으로 구분되어 줄 서 있는 순서대로 주어진다. 태양이는 원생들을 키 순서대로 줄 세웠으므로, 왼쪽에 있는 원생이 오른쪽에 있는 원생보다 크지 않다. 원생의 키는 109를 넘지 않는 자연수이다.
출력
티셔츠 만드는 비용이 최소가 되도록 K개의 조로 나누었을 때, 티셔츠 만드는 비용을 출력한다.
예제 입력 1
5 3
1 3 5 6 10예제 출력 1
3문제 풀이
n,k=map(int,input().split())
height=list(map(int,input().split()))
answer=[]
for i in range(n-1):
answer.append(height[i+1]-height[i])
answer.sort()
print(sum(answer[:n-k]))k개의 조를 나눈다는 것에 집중하기 보다는 유치원생의 키 차이를 구하는 것에 집중하면 쉽게 풀 수 있었던 문제같다.
조를 나눈다는 것은 원생의 키 차이 값을 k-1개 무시한다는 뜻이다.
즉, 모든 유치원생들의 키 차이 합을 구한뒤에 k-1개를 빼면 원하는 값을 얻을 수 있다는 뜻이다.
조를 나누어서 max, min 값의 차이를 구하려고 했으나 결국 그 값은 각 조에 포함된 모든 원생들의 키 차이의 합이기 때문에 굳이 max, min을 구할 필요가 없다.
때문에 for문을 이용하여 인접해 있는 원생들의 키 차이값을 구한 뒤, 가장 차이가 큰 값 k-1개를 빼면 정답처리가 된다.
며칠을 고민하다가 결국 풀이를 보면서 풀었던 문제이다.
답을 알고나니 너무 허무했던 기억이 난다. 그리디 알고리즘은 조금 더 간단하게 고민을 해보면 쉽게 풀리는 경우가 많은 것 같다.
