[백준] 2212 센서 (C++)

2212번: 센서

2021.11.05 기준 solved.ac 골드 5 Greedy 문제이다.

 

이 문제는 지문을 보고 문제를 이해하는 것이 쉽지 않았다. 국어를 못하긴 하지만.... 이런 내가 지문을 조금 더 이해하기 쉽게 바꿀 수 있겠다고 생각할 정도였으니.....

---

풀이

우선 문제는 대충 다음과 같다.

일직선의 고속도로에 N개의 센서가 있다. 센서가 수집한 자료를 분석할 집중국을 K개 세울 것이다. 이때, 모든 센서가 적어도 하나의 집중국의 범위에 있어야 한다. 각 집중국은 직선의 형태라고 생각하면 편하다.

 

그렇다. 이해가 잘 되지 않는다! ㅋㅋ 문제 본문의 예제 입력 1을 그림을 통해 이해해 보자!

센서가 6개 있고, 집중국을 2개 세울 것이다. 세 번째 줄은 각 센서의 위치이다.

 

센서의 위치를 그림으로 나타내면 다음과 같다.

이제 집중국 2개를 세워서 모든 센서를 포함해보자!

그중 집중국의 수신 가능 거리 영역의 거리의 합이 최소가 되게 세우면 다음과 같다!

즉, 모든 집중국의 수신 가능 영역의 합의 최소는 5(=2+3)이다.

---

이제 문제를 풀어보자. 

이번엔 본문의 예제 2를 통해 문제를 풀어보겠다.

 

이 예시의 답이 되는 상황은 아래 그림과 같다.

문제 해결의 아이디어는 다음과 같다.

K개의 집중국을 세우게 되면 집중국과 집중국 사이 빈 공간이 K-1개 생기게 된다. 이 K-1개의 빈 공간을 가장 크게 하면 된다! 즉, 센서 사이사이의 공간을 정렬하여 큰 것부터 K-1개를 제외하고 나머지 값들을 모두 더하면 답이다. 

 

센서 사이의 거리가 멀때, 그 두 센서를 포함하는 집중국을 세우면 집중국의 수신 가능 거리의 영역이 넓어지기 때문에 좋지 못하기 때문이다!

 

직접 해보자!

 

우선 입력받은 센서들의 좌표를 오름차순으로 정렬한다.

3 6 7 8 10 12 14 15 18 20

 

이 좌표들의 사이사이의 거리를 모두 추출하면 다음과 같다.

3 1 1 2 2 2 1 3 2

 

이를 내림차순으로 정렬하면 다음과 같다.

3 3 2 2 2 2 1 1 1

 

이를 큰 것부터 K-1개(이번 예시에선 3 3 2 2)를 제외하면 다음과 같다. (실제로 위 그림을 보면 우리가 제외한 사이 거리가 각각 3, 2, 2, 3인 부분이 비워져 있다.)

2 2 1 1 1

 

 

이를 모두 더한 값인 7이 답이다!!

 

---

코드

#include <bits/stdc++.h>
#define INF 9876543210
#define endl '\n'
using namespace std;
using ll = long long;

ll n, k, ans = 0;
ll sensor[10001];
ll facility[10001];

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	cin >> n;
	cin >> k;
	for (ll i = 1; i <= n; i++) cin >> sensor[i];
	sort(sensor + 1, sensor + n + 1);
	for (ll i = 1; i < n; i++) facility[i] = sensor[i + 1] - sensor[i];
	sort(facility + 1, facility + n, greater<>() );
	for (ll i = k; i < n; i++) ans += facility[i];
	cout << ans << endl;

	return 0;
}