[BOJ] 2212번_센서_정렬 (C++)

[문제]

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

일직선 상에 N개의 센서가 존재할 때, 모든 센서는 적어도 하나의 집중국과는 통신이 가능해야한다. 이때 집중국의 수신 가능 영역의 길이의 합의 최소값을 구하는 문제이다.

[사용 알고리즘]

정렬

[풀이 핵심]

• 센서는 일직선 상의 좌표로 존재하기 때문에, 오름차순으로 정렬해준다.
• 중요한 건 센서 사이의 거리이므로 모든 센서사이의 거리를 구해서 dis벡터에 저장해준다.
• 집중국과 집중국 사이의 거리는 수신 가능 영역 길이에 포함되지 않으며, 집중국이 K개 라면 집중국 사이의 거리는 K-1개 이다.
• 따라서 센서 사이의 거리중 가장 큰 값부터 K-1개를 집중국과 집중국의 사이로 사용하면 된다.

[코드]

//boj2212번_센서_정렬

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

bool compare(int x, int y) {
	return x > y;
}

int main() {
	int N, K;
	cin >> N;
	cin >> K;

	vector<int> sensor;

	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;

		if (find(sensor.begin(), sensor.end(), num) == sensor.end()) {
			sensor.push_back(num);
		}
	}

	sort(sensor.begin(), sensor.end());

	vector<int> dis;

	for (int i = 0; i < sensor.size() - 1; i++) {
		dis.push_back(sensor[i + 1] - sensor[i]);
	}

	sort(dis.begin(), dis.end(), compare);

	int result = 0;

	for (int i = K - 1; i < dis.size(); i++) {
		result += dis[i];
	}

	cout << result;

	return 0;
}