[baekjoon 2110] 공유기 설치 (이진탐색) (C++)

www.acmicpc.net/problem/2110

2110번: 공유기 설치

N개의 좌표점 위에 C개의 공유기를 설치하는 것이다.

각각의 좌표값에 공유기를 설치할 때 가장 인접한 거리 중 최댓값을 출력하는 것이다.

 

1 4 6 7 9에서 5개의 공유기를 설치한다고 하면

모든 좌표값에 설치하는 경우가 되겠다. 그리고 가장 인접한 거리는 1이 될 것이다. (6-7의 거리가 1로 가장 인접하다.)

3개를 설치한다고 가정하면 1 4 7 또는 1 4 9의 경우로 거리는 3이 될 것이다.(1-4의 거리가 3으로 가장 인접하다.)

 

이 문제를 어떻게 이진 탐색으로 풀까 고민을 많이 했다.

 

1. 이진 탐색의 주제는 위치가 아닌, 거리로 생각한다.

즉, a부터 b까지의 거리의 좌표값들에 거리 d만큼 공유기를 설치하면 총 몇 대나 설치할 수 있을까?로 접근한다.

 

2. 좌표값들을 정렬한 다음, 기준 거리를 정한다. (mid에 해당한다.)

따라서 1 4 6 7 9인 경우 mid = start + end /2 => (1 + 9) / 2 = 5이다.

이 좌표값들에 5의 간격으로 설치하는 경우는? 1과 6 or 7 or 9 / 4와 9 뿐이다. 즉 두 개밖에 설치하지 못한다.

 

3. start와 end의 갱신은?

그러면 이진 탐색에서 start 또는 end를 갱신할 때의 기준은 바로 저 공유기를 설치할 수 있는 대수이다.

간격이 넓으면 그만큼 설치할 수 있는 대수가 적어지고, 간격이 좁으면 그만큼 설치할 수 있는 대수가 많아진다.

 

이 방식으로 이진 탐색을 구현하면 된다.

 + 처음 start와 end를 초기화해줄 때 start는 1로 해야 한다. 난 처음에 좌표값들 중 최솟값으로 정해주었는데

기준거리는 말 그대로 거리이기 때문에 좌표의 최솟값으로 계산하면 거리의 갱신이 이상하게 된다.

(예시, 5 5 101 102 103 104 105) -> 정답은 1이지만 start를 최솟값 101로 정해버리면 탐색이 되지 않는다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, c, x;
vector<int> v;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> c;
	for (int i = 0; i < n; i++) {
		cin >> x;
		v.push_back(x);
	}
	sort(v.begin(), v.end());

	int start = 1;
	int end = v[n-1];

	while (start <= end) {
		int cnt = 1;
		int mid = (start + end) / 2;


		int t = v[0];
		for (int i = 1; i < n; i++) {
			if (v[i] - t >= mid) {
				cnt++;
				t = v[i];
			}
		}
		if (cnt >= c) {
			start = mid + 1;
		}
		else {
			end = mid - 1;
		}
	}

	cout << end;
}