백준 2212번 센서

문제 링크입니다: https://www.acmicpc.net/problem/2212

2212번: 센서

센서의 위치를 정렬하고 서로의 인접 거리를 계산합니다.

이후 기지국을 인접 거리가 긴 위치 순서대로 K개 배치하면 수신 가능 영역의 거리의 합의 최솟값을 구할 수 있습니다.

예외 사항으로는 K가 N 이상일 경우이므로 미리 처리해줍니다.

	#include <iostream>
	#include <vector>
	#include <algorithm>
	using namespace std;
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N, K;
	cin >> N >> K;
	vector<int> v(N);
	for (int i = 0; i < N; i++)
	{
	cin >> v[i];
	}
	// 예외 처리
	if (K >= N)
	{
	cout << "0";
	return 0;
	}
	sort(v.begin(), v.end());
	vector<int> diff(N - 1);
	for (int i = 0; i < N - 1; i++)
	{
	diff[i] = v[i + 1] - v[i];
	}
	sort(diff.begin(), diff.end());
	int result = 0;
	for (int i = 0; i < N - K; i++)
	{
	result += diff[i];
	}
	cout << result << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~