Boj 13164) 행복유치원

문제

백준 13164

설명

아이들은 키에 대한 오름차순으로 줄 서 있고 우리는 연속된 K 개의 조을 만들어야 한다. 이때의 비용은 조원의 키의 최댓값에서 최솟값을 뺀 값이 된다. 이를 어떻게 풀면 좋을까?

처음에 아이들 각각 혼자서 조를 이룬다고 해보자. 그러면 아이들의 수인 N 개의 조가 있을 것이고 키 차이가 없으므로 총 비용은 0 이 된다. 여기서 N-K 번 조을 합치면 우리가 원하는 K 개의 조가 남게 된다.

조 A 와 B 가 있어서 새로 A+B 조를 만든다고 하자. 새로운 조의 비용은 아이들이 키 순서대로 서있으므로 A 의 오른쪽 끝과 B 의 왼쪽 끝 아이의 키 차이만큼 늘어나게 된다. 그러면 그리디 전략을 사용해 아이들의 키 차이가 작은 순서대로 N-K번 그룹을 합치면 가장 작은 비용으로 답을 구할 수 있다.

시간 복잡도

O(\(\mathrm{N} \log{\mathrm{N}}\))

코드

int n, k, arr[300001];
map<int, int> dist_map;

int main()
{
	fastio;

	cin >> n >> k;
	
	int tmp1, tmp2;
	cin >> tmp1;
	for (int i = 1; i < n; i++)
	{
		cin >> tmp2;
		dist_map[tmp2 - tmp1]++;
		tmp1 = tmp2;
	}
	
	int ans = 0;
	int cnt = n - k;
	if (cnt)
		for (auto pair : dist_map)
		{
			ans += pair.first * min(cnt, pair.second);
			cnt = cnt - min(cnt, pair.second);
			if (cnt <= 0) break;
		}
	
	cout << ans;
}