백준 13164 행복 유치원 C++

 

간단한 해설

 

 다음과 같은 문제에서는 조를 k개의 조로 나누고, 그 조의 최댓값과 최솟값의 차가 비용이다.

그리고 그 차의 합이 최소가 되는 값을 구해야 한다.

 

그러면 우리가 그 값을 어떻게 생각해야할까?

 

5 3
1 3 5 6 10

다음과 같이 값이 주어졌다고 생각해보자.

 

그러면 당연히 5와 6을 묶고, 그리고 제일 차이가 적어보이는 3이랑 묶어서 1 / 3 5 6 / 10 또는, 1 3 / 5 6 / 10 이런 두 가지 경우의 수가 나올 것이다.

 

여기서 지목해야 하는 것은 값의 차이이다.

 

값의 차이를 기준으로 묶으면 된다.

그러면 값의 차이를 기준으로 입력값을 다음과 같이 나타낼 수 있다.

 

// 이전
1 3 5 6 10

// 이후
 2 2 1 4

 

이렇게보니까 뭔가 감이 잡힌다.

아까 내가 임의로 선택한 방식이 어떤 방식인지 보인다.

 

결국 값의 차이를 제일 적은거부터 N - K 개 뽑으면 정답이다.

답

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define ll long long
using namespace std;
int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	ll n,k;
	cin>>n>>k;
	vector<ll> v(n);
	for(int i=0;i<n;++i){
		cin>>v[i];
	}
	vector<ll> tmp(n-1);
	priority_queue<ll> q;
	for(int i=0;i<n-1;++i){
		tmp[i]=v[i+1]-v[i];
		q.push(-tmp[i]);
	}
	ll gae=n-k,ans=0;
	while(gae>0){
		ll val=-q.top();
		q.pop();
		ans+=val;
		--gae;
	}
	cout<<ans;
}