문제링크 : 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";
}
'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 |
댓글