BOJ 2212 센서

BOJ 2212 센서

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

요약

센서의 개수와 집중국(센서가 수집한 자료를 모으고 분석하는 넘)의 개수가 주어지고 평면 선에서의 센서의 위치가 주어졌을 때, 집중국을 이 평면선에서 설치할때 집중국들의 센서 수신 거리의 합의 최솟값을 출력하는 문제.

풀이

센서가 입력되는 순서는 의미가 없기 때문에 일단 정렬해 준다.

어떤 두 점 사이에서 집중국이 있으면 집중국이 그 사이에 어디 있든 간에 센서 수신 거리는 두 점 사이의 거리이다.

즉 집중국이 한 개 있다면 양 끝에 있는 센서 사이의 거리가 답일 것이다. 집중국이 두 개 있다면 두 구역으로 나눠서 센서의 거리를 줄일 수 있을 것이다. 센서들 사이의 거리중에서 가장 먼 거리를 제외하고 두 구역으로 나누는 게 가장 크게 거리를 줄일 수 있을 것이다.

위의 예제를 예시로 3~6사이의 거리가 젤 멀기 때문에 제외하고 거리를 구해보면 총 5가 나오게 된다.

이 말 그대로 구현했으나 런타임 에러가 났다… 원인을 찾아보니 숫자보다 기지국 개수가 더 많아지는 경우를 생각을 안 해서 기지국의 개수-1만큼 길이를 빼주었는데 queue가 비었는데도 pop 하게 되었다. 그래서 기지국 개수가 더 많이 주어지면 0을 출력하게 예외 처리해 주었다.

코드

#include<iostream>
#include<vector>
#include<queue>;
#include<algorithm>
using namespace std;
vector<int>q;
priority_queue<int>pq;
int n, k,num;
int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> num;
		q.push_back(num);
	}
	if (n < k) {
		cout << "0" << "\n";
		return 0;
	}
	sort(q.begin(), q.end());
	int ans = 0;
	for (int i = 1; i < q.size(); i++) {
		pq.push(q[i] - q[i-1]);
		ans += q[i] - q[i-1];
	}
	for (int i = 0; i < k - 1; i++) {
		ans -= pq.top();
		pq.pop();
	}
	cout << ans << "\n";
}