본문 바로가기
BOJ

BOJ 2212 센서

by 홍code 2022. 3. 10.

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

 

2212번: 센서

첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있

www.acmicpc.net

요약

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

풀이

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

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

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

위의 예제를 예시로 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";
}

'BOJ' 카테고리의 다른 글

BOJ 15748 Rest Stops  (0) 2022.03.10
BOJ 13904 과제  (0) 2022.03.10
BOJ 11000 강의실 배정  (0) 2022.03.10
BOJ 1931 회의실 배정  (0) 2022.03.10
BOJ 17509 And the Winner Is... Ourselves!  (0) 2022.03.10

댓글