[C/C++] 백준 2110번 - 공유기 설치

 

 

 

<코드>

#include<iostream>
#include<algorithm>
using namespace std;

int N, C;
int low, mid, high, cnt, tmp, d, ans;
int home[200001];

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

	low = 1; // 최소거리
	high = home[N - 1] - home[0]; // 최대거리

	while (low <= high)
	{
		cnt = 1; // 두 공유기 사이의 거리를 최대로 하기 위해서는 첫번째 집에는 공유기가 설치되어야 함.
		tmp = home[0];
		mid = (low + high) / 2;

		for (int i = 1; i < N; i++)
		{
			d = home[i] - tmp;
			if (mid <= d)
			{
				cnt++;
				tmp = home[i];
			}
		}

		if (cnt >= C) // 계산된 공유기수 >= 설치할 공유기수
		{
			// 공유기 간의 간격을 늘립니다.
			ans = mid;
			low = mid + 1;
		}
		else // (cnt < C)  계산된 공유기수 < 설치할 공유기수
		{
			// 공유기 간의 간격을 줄여야 합니다.
			high = mid - 1;
		}

	}

	cout << ans;

}

 

풀이 방법

처음의 최소 간격을 1로, 최대 간격을 양 끝 집 사이의 거리로 설정한다. 그런 뒤 이분 탐색 방법을 이용하여 mid값을 구한 뒤 간격 기준을 mid로 하였을 때 mid간격으로 공유기를 최대 몇 개 설치할 수 있는지 count 하고 그 값과 처음에 입력으로 받은 설치해야 할 공유기 수 C와 비교하여 Low값과 High값을 조정합니다. 

 

 

 

www.acmicpc.net/problem/2110

2110번: 공유기 설치