[백준/2110번/C++] 공유기 설치

공유기 설치

---

문제 )

---

입출력 )

---

예제 입력 )

---

풀이 )

이 문제는 간단히 설명해서 주어진 공유기 수(C)를 효율적으로 사용하기 위해 최적의 공평한 간격을 구해야 하는 개념입니다.

 

우선 맨 처음 집은 무조건 설치 된다고 보면 오른쪽을 줄여 나가면서 최적의 간격을 먼저 구합니다. 그 간격으로 설치했을 때 설치한 개수가 주어진 개수와 같은지, 최대인지 확인하여 최대의 거리를 구합니다.

 

예제를 보면 5개의 집에 3개의 공유기입니다.

이분 탐색으로 간격을 구해보면

○ : 설치X        ● : 설치O
간격 4 : 1 2 4 8 9  ● ○ ● ○ ○ (1, 4, 9)
간격 2 : 1 2 4 8 9  ● ○ ● ● ○ (1, 4, 8)
간격 3 : 1 2 4 8 9  ● ○ ● ● ○ (1, 4, 8)

이분 탐색으로 간격을 구해보면 조건을 만족하는 최대 거리는 3이 됩니다.

---

코드 )

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

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

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> c;
	for (int i = 0; i < n; i++)
	{
		cin >> num;
		v.push_back(num);
	}
	sort(v.begin(), v.end());
    
	int left = 1, right = v[n-1] - v[0], mid;
	int r = 0;
	while (left <= right)
	{
		mid = (left + right) / 2;
		int cnt = 1;
		int prev = v[0];

		for (int i = 1; i < n; i++)
		{
			if (v[i] - prev >= mid)
			{
				cnt++;
				prev = v[i];
			}
		}

		if (cnt >= c)
		{
			r = max(r, mid);
			left = mid + 1;
		}
		else right = mid - 1;
	}
	cout << r;
}

 

---

코드 설명

---

이분탐색을 통해 공평한 간격을 구할 수 있습니다.

이 문제는 왼쪽을 고정시키고 오른쪽을 줄여나가면서 적정 거리를 구하는 문제입니다.

 

(이분탐색 하기 전 정렬은 기본!!)

우선 이분탐색 한 값은 거리이고 예제를 예시로 들면 중간 값 4좌표가 처음 간격으로 주어지고 집과 집 사이 좌표 사이 거리가 4 이상일 때 cnt를 +1 해서 설치하면 설치 개수가 2개이기 때문에 조건을 확인 해보면 간격 2는 맞지 않는다는 것을 알 수 있습니다.

 

이어서 다시 이분탐색을 하면 간격이 2가 나오고 2 간격으로 설치하면 3개 모두 설치가 됩니다. 하지만 cnt가 같거나 클 때는 left를 올려서 간격을 늘려 간격이 3일 때를 구해보면 3개 모두 설치가 된다. 그러고 간격이 4일 때는 아니었으니까

최대거리가 3이 나옵니다.

---