[백준/c++] 13164 행복 유치원

문제

행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다.

이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자.

입력

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

출력

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

구현해야 할 조건

가장 비용이 적게 들어갈 만큼 K조를 짜서 만들자!

일단, 배열에서 K개를 만들기 위해선 K-1번 잘라야한다는 것은 국룰이다. 여기에서 생각할 수 있다! 그렇다면 가장 차이가 안나게 자를 수 있는 방법은 무엇일까?

오름차순으로 정렬되어있기 때문에, 양 옆에 차이가 나거나 동률이다. 이 점에서 동률이라면 계속해서 흘러 가도 그만이겠고, 하지만 그 차이가 모든 배열을 비교했을때 크다면? 당연히 차이도 어마어마 하겠다! 그렇다면 가장 큰 놈들로
K-1번 자르는것이 맞다. N또한 30만이기 때문에 (nlogN)으로 해결을 해야하기 때문에 그리디가 딱 맞다.

code

#include<iostream>
#include<algorithm>
#include<vector>

#define MAX 300001
using namespace std;

int n,k;
int arr[MAX];

int main(){
	
	cin >> n >> k;
	
	for(int i = 0; i < n; i++)
		cin >> arr[i];
	
	vector<int> v;

	for(int i = 0; i < n-1; i++){
		
		int num = arr[i+1] - arr[i];
		v.push_back(num);
		
	}
	sort(v.begin(),v.end(),greater<int>());
//	
//	for(int i = 0; i < v.size(); i++)
//		cout << v[i] << " ";
//		
//	cout << endl;
	
	int ans = 0;
	
	for(int i = k-1; i < v.size(); i++)
		ans += v[i];
		
	cout << ans;
	
	
	return 0;
}