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

문제

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

 

어려운 문제는 아닌데 뭔가 이해하는데 오래걸렸다.

아래와 같이 생각하니 한방에 이해가 갔다

 

주의사항

K값이 N값보다 클 경우를 생각해야한다!!! 이걸 생각 못해서 런타임 에러 났다.

결과값은 long long으로

 

풀이

 

예시 2번)

3 6 7 8 10 12 14 15 18 20에 센서들이 있다.

센서들 사이의 거리를 확인한다. 3 1 1 2 2 2 1 3 2

이것을 내림차순 정렬한다. 3 3 2 2 2 2 1 1 1

K-1 즉 4개를 삭제한다 2 2 1 1 1

이것을 다 합하면 result 7 이 나온다

 

센서들 사이의 거리가 긴부분은 나눠서 집중국을 설치해주면 되기 때문이다.

 

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

int main()
{
	int N, K,num;
	cin >> N >> K;

	//K>=N/////////////////////////////////
	if (K >= N) {cout << "0";return 0;	}

	//INPUT////////////////////////////////
	vector<int>g;
	for (int i = 0; i < N; i++)
	{
		cin >> num;
		g.push_back(num);
	}
	sort(g.begin(), g.end());
	g.erase(unique(g.begin(), g.end()), g.end());
	

	//DISTANCE/////////////////////////////
	vector<long long>dis;
	for (int i = 0; i < g.size()-1; i++)
	{ dis.push_back(g[i + 1] - g[i]); }
	sort(dis.begin(), dis.end(),greater<int>());
	dis.erase(dis.begin(), dis.begin() + (K - 1));


	//RESULT///////////////////////////////
	long long result = 0;
	for (int i = 0; i < dis.size(); i++) { result += dis[i]; }
	cout << result;
}