[BOJ]2110번: 공유기 설치 (c++)

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

2110번: 공유기 설치

 

 

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

using namespace std;

// 라우터를 거리가 서로 min_gap 이상으로 설치할 때의 개수 구하기
int count_routers(vector<int> &houses, int min_gap)
{
	int last = houses[0];
	int cnt = 1;

	for (int i = 1; i < houses.size(); ++i)
	{
		if (houses[i] - last >= min_gap)
		{
			++cnt;
			last = houses[i];
		}
	}

	return cnt;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 입력
	int N, C;
	cin >> N >> C;
	vector<int> houses(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> houses[i];
	}

	// 이분탐색을 위한 정렬
	sort(houses.begin(), houses.end());

	// 이분탐색
	int left = 1;
	int right = houses.back() - houses.front();
	int answer = 0;
	while (left <= right)
	{
		int mid = (left + right) / 2;
		int cnt =  count_routers(houses, mid);

		/*
			최소간격이 mid일때 설치개수가 C이상이면, 
			간격을 더 늘릴 수 있는지 확인한다
		*/
		if (cnt >= C)
		{
			answer = max(mid, answer);
			left = mid + 1;
		}
		else
		{
			right = mid - 1;
		}
	}

	cout << answer;

	return 0;
}

 

 

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다.
둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

 

주어진 N개의 좌표에 C개의 공유기를 설치하는데,

이때 가장 인접한 두 공유기 사이의 거리가 최대가 되어야 한다.

 

그런데 주어진 수의 제한이 다들 크기 때문에, 순열조합이나 반복문으로 값을 찾기가 어렵다.

그래서 이분탐색으로 답을 찾는 것이 시간복잡도를 최대한 줄이는 방법이다.

 

 

이 때 인접한 두 공유기 사이의 거리와 설치 가능한 공유기의 개수는 서로 영향을 받는다. 

최소 인접거리를 mid라고 했을 때,

이전에 설치된 공유기와의 거리가 mid 이상인 집에만 공유기를 설치할 수 있다.

따라서 최소 인접거리가 mid일 때의 공유기의 개수 cnt를 기준으로 이분탐색을 진행한다. 

while (left <= right)
{
	int mid = (left + right) / 2;
	int cnt =  count_routers(houses, mid);

	/*
		최소간격이 mid일때 설치개수가 C이상이면, 
		간격을 더 늘릴 수 있는지 확인한다
	*/
	if (cnt >= C)
	{
		answer = max(mid, answer);
		left = mid + 1;
	}
	else
	{
		right = mid - 1;
	}
}