백준 2212 / cpp / c++

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

이 문제의  경우 풀이는 매우 쉽다.

우리는 중계기를 설치  할건데 이 중계기의 빈공간의 합이 최소가 되게 고르면 된다 그이유는 일단 중계기는 어떠한 점이 아닌 직선형의 중계기 이다 

빈 공간은 무조건 우리가 설치한 센서들의 갯수인 n-1 개 만 설치가 된다

즉 이 n-1개의 빈공간 들중 우리는 가장 큰 영역을 제외해주어야 한다 근데  센서 2개로 영역을 고른다고 가정 할 때 우리가 결국 포기해야하는 영역들 중 이영역을 k개로 나누기 위해서는 결국 k-1개의 공간은 포기를 해야한다

#include <iostream>
#include <algorithm>
#include <vector>
int n, k;
using namespace std;
vector<int> sensors;
vector<int> spaces;
int main() {
	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		sensors.push_back(tmp);
	}

	sort(sensors.begin(), sensors.end());
	int beforeSensor = sensors[0];
	for (int i = 1; i<sensors.size(); i++) {
		spaces.push_back(sensors[i] - beforeSensor);
		beforeSensor = sensors[i];
	}
	
	sort(spaces.begin(), spaces.end());

	int sum = 0;
	
	for (int i = 0; i < (int)spaces.size() -  (k-1); i++) {
		sum += spaces[i];
	}

	cout << sum;
}