문제
행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다.
이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자.
입력
입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들의 키를 나타내는 N개의 자연수가 공백으로 구분되어 줄 서 있는 순서대로 주어진다. 태양이는 원생들을 키 순서대로 줄 세웠으므로, 왼쪽에 있는 원생이 오른쪽에 있는 원생보다 크지 않다. 원생의 키는 109를 넘지 않는 자연수이다.
출력
티셔츠 만드는 비용이 최소가 되도록 K개의 조로 나누었을 때, 티셔츠 만드는 비용을 출력한다.
입력 예시
5 3
1 3 5 6 10
출력 예시
3
문제 해결 포인트
각 원생간 키 차이를 리스트화 시킴 -> 작은 순으로 정렬 -> 가장 작은 차이부터 n-k개까지의 차이를 더한 값이 최소 비용임.
혼자 풀다가 도저히 풀리지 않아서 해석을 찾아다녔다. 코드 자체는 간단했지만 문제 해결 포인트에 적어 놓, 기울임 표시한 저 가장 작은 차이부터 n-k개까지의 차이를 더한 값 말이 이해가 안 가서 한참 헤맸다. 역시 내 수포자 짬바 어디 안가죠 왜 0부터 n-k의 값을 더해줘야 하는가? 를 이해하기 위해 손으로 직접 데이터를 그려가며 겨우 이해한 문제.
코드
# BOJ Greedy 13164
# 행복유치원
n, k = map(int, input().split()) # n : 원생 수, k : 조의 수
students = list(map(int, input().split())) # 유치원생의 키
costs = []
for i in range(n-1) :
costs.append(students[i+1] - students[i]) # 학생들 간 차이를 구해서 costs에 대입
costs.sort() # 차이가 적은 순서대로 정렬
print(sum(costs[:n-k])) # 0부터 n-k-1 즉 0~1의 값을 더한다.