언제나 처음처럼

[문제 링크]

이분 탐색의 조건을 어떻게 만족하는지 이해하느라 고생했던 문제였다.

가장 인접한 두 공유기 사이의 거리가 멀어질수록 설치하는 공유기의 개수는 작아진다. 즉, 반비례한다.

알고리즘은 다음과 같다.

집의 좌표를 vector에 입력받고, 오름차순 정렬한다.

start를 1로, 가장 작은 좌표와 가장 큰 좌표 사이의 거리를 end로 정하고 이분 탐색을 시작한다.

가장 인접한 두 공유기 사이의 거리가 최소 mid 이상이라고 했을 때, 설치할 수 있는 공유기의 개수가 만약 설치하고자 하는 개수(C)보다 많거나 같다면  조건을 만족하는 것이기 때문에 이 때의 가장 인접한 두 공유기 사이의 거리 (mid로 갱신하는 것이 아님!!) 을 결과값으로 갱신하고, 더 멀리했을때도 조건을 만족하는지 알아보기 위해 start를 mid+1로 바꿔준다.

(더 많이 설치된 경우도 조건을 만족하는 이유는 공유기를 갯수에 맞게 제거해도 가장 인접한 거리는 변함이 없기 때문)

반대로 설치하고자 하는 개수(C)보다 적다면 조건을 만족하지 않기 때문에 mid 이상의 거리는 무조건 조건을 만족하지 않는다는 사실을 알 수 있다. 따라서 결과값을 갱신하지 않고, mid를 줄이기 위해 end를 mid-1로 바꿔준다.

start가 end보다 커질 때까지 위 작업을 반복하게 되면 결과값에는 가장 인접한 두 공유기 사이의 거리가 최대인 경우가 저장된다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; 
const int MAX = 987654321;

int main(void)
{
	int N, C;
	cin >> N >> C;
	
	vector<int> router(N);
	for (int i = 0; i < N; i++)
		cin >> router[i];
	
	sort(router.begin(), router.end());

	int start = 1, end = router[N - 1] - router[0], result;
	while (start <= end)
	{
		int mid = (start + end) / 2;
		int here = 0, cnt = 1, minDist = MAX;
		for (int i = 1; i < N; i++)
		{
			int dist = router[i] - router[here];
			if (dist < mid) continue;
			minDist = min(minDist, dist);
			here = i;
			cnt++;
		}

		if (cnt >= C)
		{
			result = minDist;
			start = mid + 1;
		}
		else
			end = mid - 1;
	}

	cout << result << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 47 day