백준 13164 행복 유치원(c++)

https://www.acmicpc.net/problem/13164

13164번: 행복 유치원

<코드>

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int n,k;
	cin>>n>>k;
	vector<int>v;
	for(int i=0;i<n;i++)
	{
		int a;
		cin>>a;
		v.push_back(a);
	}
	vector<int>cost;
	for(int i=1;i<v.size();i++){
		cost.push_back(v[i]-v[i-1]);
	}
	sort(cost.begin(),cost.end());
	int sum = 0;
	int cnt=0;
	for(int i=0;i<n-k;i++)
	{
		sum += cost[i];
		
	}
	cout<<sum<<'\n';
	
	
}

<풀이과정>

n=5 k=3 배열 2 5 6 7 8이라고 가정

비용의 합이 최소가 되기위해서 우선적으로 비용 벡터 cost에 각각의 비용 v[i]-v[i-1]을 저장한다.

저장한 후           2 5 6 7 8

   차이 v[i]-v[i-1]   3 1 1 1 중 가장 작은 것을 두 개(n-k) 선택하면 된다.

즉 1 두개를 선택하면 비용의 합의 최소값은 2가 된다.

2 / 5 6 / 7 8 로 나눠도 되고  2 / 5 6 7 / 8로 나눠도 비용의 합의 최솟값은 2가 된다.