[BOJ 2212 // C++] 센서

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2212번 문제인 센서이다.
문제는 아래 링크를 확인하자.

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

2212번: 센서

집중국이 하나라면, 수신가능영역은 모든 센서를 전부 덮는 단일 구간이 필요하게 된다.

집중국이 둘이라면, 수신가능영역은 센서들 사이의 거리 중 가장 먼 거리를 제외한 거리를 덮을 때 가장 적은 구간을 덮게 된다.

집중국이 N+1개라면, 수신가능영역은 센서들 사이의 거리중 가장 먼 N개의 거리를 제외한 거리를 덮을 때 가장 적은 구간을 덮게 될 것이라는 것을 알 수 있다.

 

이를 정렬을 이용하여 구현하면 이 문제를 해결할 수 있다.

 

아래는 제출한 소스코드이다.

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

int arr[10000];
int dist[10000];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, K; cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	sort(arr, arr + N);

	for (int i = 1; i < N; i++) {
		dist[i] = arr[i] - arr[i - 1];
	}

	sort(dist, dist + N);

	int ans = 0;
	for (int i = 1; i <= N - K; i++) {
		ans += dist[i];
	}

	cout << ans;
}