BOJ 13164 행복 유치원

greedy문제(?)이다. 정답률도 높고, 실제로 어렵지는 않지만 생각 좀 해야하는 문제이다.
그리고 나는 sksdong1님께 풀이 힌트를 받은 상태에서 풀었기 때문에 빨리 풀 수 있었다.

오름차순으로 주어진 수들을 k개의 그룹으로 나눠 묶었을 때(한 그룹에 1명 이상), 각 그룹에서 최대값과 최소값의 차이를 계산하고, 그 계산한 값들의 합을 최소가 되게 하라는 문제인데, 각 그룹에서 최대값과 최소값의 차이는 (오름차순으로 정렬돼있으므로) 각 그룹의 맨 오른쪽 값과 맨 왼쪽 값의 차이가 된다.

얼핏 보면 k개의 그룹으로 나눌 수 있는 경우를 다 해봐야하나 라는 생각이 들 수 있지만, 잘 생각해보면 간단하다. 위에서 말했듯이, 각 그룹의 맨 오른쪽 값과, 맨 왼쪽 값의 차이가 각 그룹의 비용인데, 이 것은 맨 오른쪽 값과 맨 왼쪽 값의 차이이기도 하지만, 그 그룹에 포함된 수들 중 인접한 수들의 차이의 합이기도 하다.
인접한 수들의 차이의 합을 최소로 해야하고, 또한 그룹으로 묶으므로써 그룹과 그룹의 경계에 있는 수들의 차이는 계산에 넣지 않게 된다. 즉 그룹을 지을 때, 인접한 수들의 차이가 큰 곳을 그룹의 경계로 만들어야 구하는 값이 최소가 될 수 있다.

결국 구하는 최소값은 인접한 수들의 차이들을 구하고 내림차순으로 정렬해서 가장 큰 k-1개의 값(인접한 수들의 차이)을 제외한 나머지의 합이 된다.