[백준/2110] 공유기 설치 (이분 탐색)

1. 문제

 

 

 

 

2. 접근 방법

이분 탐색의 종류인 Parametric Search 를 이용한 문제이다.

이 문제는 다음과 같은 과정으로 접근해야 한다.

 

(1) 공유기 사이의 최소 거리가 될 수 있는 값은, 1 이다.

(2) 공유기 사이의 최대 거리가 될 수 있는 값은, (마지막 공유기의 위치 - 첫 번째 공유기의 위치) 이다.

(3) 중간값은 (1)과 (2)에서 구한 값의 중간값이다.

(4) 중간값이 가능한 값인지 검사한다.

(5) 만약, 중간값이 가능한 값이라면 → 범위를 큰 쪽으로 줄인다.

(6) 만약, 중간값이 불가능한 값이라면 → 범위를 작은 쪽으로 줄인다.

 

여기에서 중간값이 가능한 값인지는 다음과 같이 구할 수 있다.

전체 공유기를 대상으로, 자신의 공유기의 위치에서 이전에 놓았던 공유기의 위치를 뺀 값이 중간값보다 크다면 놓는다.

 

즉, 만약 집의 위치가

 

1, 2, 4, 8, 9 

 

라고 가정한다면,

First 값은 1,

Last 값은 (9 - 1) = 8,

중간값은 (8 - 1) / 2 = 3.5 (3)

가 되고, 이들 값에 대해서 이분 탐색을 실시하는 것이다.

 

 

 

 

3. 구현

#include <iostream>
#include <algorithm>

using namespace std;

int N, C;
int home[200000];
int f = 1, l, m;
int res;

bool isPossible(int d)
{
	int cnt = 1;
	int lastLoc = home[0];

	for (int i = 0; i < N; i++)
	{
		if (home[i] - lastLoc >= d)
		{
			lastLoc = home[i];
			cnt++;
		}

		if (cnt == C) return true;
	}

	return false;
}

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

	cin >> N >> C;
	for (int i = 0; i < N; i++) cin >> home[i];
	sort(home, home + N);

	l = home[N - 1];
	res = (f + l) / 2;
	for (;;)
	{
		if (f > l) break;

		m = (f + l) / 2;

		if (isPossible(m))
		{
			res = m;
			f = m + 1;
		}
		else
		{
			l = m - 1;
		}
	}

	cout << res << '\n';

	return 0;
}