[백준] C++ 13164(행복 유치원)

 

#include <iostream>
#include <algorithm>

using namespace std;

int arr[300001];
int gap[300001];

int main(void)
{
	int N=0;
	int K=0;
	
	cin>>N>>K;
	
	for(int i=0; i<N; i++)
	{
		cin>>arr[i];
	}
	
	int sum=0;
	
	for(int i=0; i<N-1; i++)
	{
		gap[i]=arr[i+1]-arr[i];
		sum+=gap[i];
	}
	
	sort(gap,gap+(N-1));
	
	for(int i=0; i<K-1; i++)
	{
		sum-=gap[N-2-i];
	}
	
	cout<<sum;
	

	return 0;
}

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

키는 순서대로 주어지고 조에서 키 차이만큼 티셔츠 제작 비용이 든다고 한다.

그리디 하게 접근해 보자.

예제를 보겠다.

키 차이를 나타낸 그림이다.

만약 조의 개수가 1개라면?? 비용은 어떻게 될까??

비용은 9가 된다.

그러면 조의 개수가 2개일 때는 비용은 어떻게 구하지??

여기서 아이디를 떠올려야 한다. 조의 개수가 1개에서 2개가 될 때 비용을 최소로 하는 방법은??

키 차이가 가장 큰 원생을 분리하면 된다.

 

조의 개수가 3개가 되면??

그다음으로 키 차이가 가장 큰 원생을 분리하면 된다.

생각보다 간단한 문제이다.

어떻게 문제를 해결할지 아이디어만 떠올리면 정말 금방 풀 수 있다.

 

풀이 순서

1. 키 차이를 배열에 넣고 정렬한다.

2. 키 차이가 큰 원생끼리 분리시킨다.