[백준] C++ 2212(센서)

#include <iostream>
#include <algorithm>

using namespace std;

int arr[10001];
int gap[10001];

int main(void)
{
	int N=0;
	int K=0;
	cin>>N>>K;
	
	for(int i=0; i<N; i++)
	{
		cin>>arr[i];
	}
	
	sort(arr,arr+N);
	
	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++)
	{
		if(N-2-i>=0)
		{
			sum-=gap[N-2-i];
		}
		
	}
	
	cout<<sum;
	
	return 0;
}

최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력하는 문제이다.

센서는 적어도 하나의 집중국에 연결되어야 한다.

 

해결 방법

1. 센서의 좌표를 정렬한다.

2. 센서의 좌표 사이의 거리를 구한다.

3. 좌표 사이의 거리를 정렬한다.

4. 집중국 (개수-1)만큼 gap에서 가장 큰 값을 제거해준다.

 

집중국이 1개이면 최솟값은??

 

1에서 9까지의 거리 8이다.

 

집중국의 개수가 2개이면??

 

좌표 사이 거리가 가장 먼 3에서 6을 끊이면 거리는 5가 된다.

 

집중국의 개수가 센서의 개수보다 많을 수 있기 때문에

if(N-2-i>=0) 
{
	sum-=gap[N-2-i];
}

범위 검사를 해주어야한다.

 

다른 코드

#include <iostream>
#include <algorithm>

using namespace std;

int arr[10001];
int gap[10001];

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