[Baekjoon] 2110번: 공유기 설치

 

 

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

2110번: 공유기 설치

 

---

 

문제 해결 과정

착안

공유기를 설치했을 때 가장 인접한 두 공유기 사이의 거리의 최댓값을 찾기 위해, 이진 탐색(binary search, 이분 탐색)을 응용하여 문제를 해결하고자 하였다.

 

구현

입력받은 $N$ 개의 집 좌표를 배열 Houses[]에 저장하여 오름차순으로 정렬하면, 가장 인접한 두 공유기 사이의 거리를 $c$ 라고 했을 때 설치하는 공유기의 수에 따라 $1 \leq c < c_{max} + 1 = $ Houses[$N-1$] - Houses[$0$] $+ 1$ 이다.

 

따라서, 공유기 간격을 $c$ 이상으로 하여 원하는 $C$ 개의 공유기를 모두 설치 가능한 경우는 간격을 늘려 다시 탐색하고, 그렇지 않은 경우에는 공유기 간격을 줄여 다시 탐색하는 과정을 반복하도록 구현하였으며, 이 과정에서 설치 가능 여부를 판단하는 함수를 구현해 활용하고, 이진 탐색 알고리즘을 응용하여 공유기 간격의 최댓값을 탐색하였다.

 

이진 탐색을 통해 공유기들 사이의 최소 간격 $c$를 구하기 위해, 최초 시작 시의 탐색 구간의 오른쪽 끝 값은 $c_{max}$보다 큰 값으로 설정(불가능한 값으로 설정)해야 하는 점과, 이진 탐색의 결과로 탐색 구간이 수렴하는 값은 실제로 구하는 답보다 1 만큼 큰 값임에 유의하여 구현하였다.

* 참고) 간단한 원리 설명 참고 링크.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <algorithm>

using namespace std;

int N, C;
int Houses[200000];

bool CanInstall(int c, int interval)
{
	int start = Houses[0];
	c--;

	for (int house : Houses)
	{
		if (house - start < interval)
			continue;
		
		start = house;
		if (--c == 0)
			return true;
	}

	return false;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

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

	int Min = 1;
	int Max = Houses[N - 1] - Houses[0] + 1;

	while (Min < Max)
	{
		int middle = (Min + Max) / 2;
		if (CanInstall(C, middle))
			Min = middle + 1;
		else
			Max = middle;
	}

	cout << Max - 1 << "\n";
	return 0;
}

 

실행 결과