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

2110번: 공유기 설치

 

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

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

입력

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

5 3
1
2
8
4
9

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

3

 

풀이

이분 탐색을 사용하여 푸는 문제입니다.

 

지금껏 풀어왔던 이분 탐색 문제와는 다소 차이가 있는 색다른 유형의 문제였습니다.

 

때문에 이분 탐색을 어느 부분에서 어떤 식으로 적용해야 할지 감이 잡히지 않아 다른 블로그를 참고하여 이해한 뒤 코드를 작성하였습니다.

---

/*
* 단순 반복문을 통해 풀이할 경우 시간 초과가 발생
* 시간 복잡도를 줄이기 위해 이분 탐색을 수행
*/

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

using namespace std;

int n, c;
int ans = 0;
vector<int> houses;

void input()
{
	cin >> n >> c;

	for (int i = 0; i < n; ++i)
	{
		int temp;
		cin >> temp;

		houses.push_back(temp);
	}

	sort(houses.begin(), houses.end());		// 이분 탐색을 위해 정렬 수행
}

void solve()
{
	int left = 1; 							// 최소 간격
	int right = houses[n - 1] - houses[0];  // 최대 간격

	// 이분 탐색
	while (left <= right)
	{
		int dist = (left + right) / 2;	// 공유기 사이의 간격
		int cnt = 1;					// 설치한 공유기 개수

		int prev = houses[0];
		for (int i = 1; i < n; ++i)
		{
			// 이전 집에 공유기를 설치할 경우 조건을 충족하는지 체크
			if (houses[i] - prev >= dist)
			{
				++cnt;				// 해당 집에 공유기 설치
				prev = houses[i];	// 이전 집 갱신
			}
		}

		// 설치한 공유기의 수가 조건보다 많거나 같을 경우
		// 간격을 더 크게 설치할 수 있는 경우가 있을 수 있으므로
		if (cnt >= c)
		{
			ans = max(ans, dist);	// 출력값 갱신

			// left 값을 증가시키므로써 공유기 사이 간격을 증가시킨 후 다시 이분 탐색
			left = dist + 1;
		}
		// 설치한 공유기의 수가 조건보다 적을 경우
		else
			// right 값을 감소시키므로써 공유기 사이 간격을 감소시킨 후 다시 이분 탐색
			right = dist - 1;
	}
}

void init()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}

int main()
{
	init();
	input();
	solve();

	cout << ans << '\n';

	return 0;
}​