[BOJ] 2110번 | 공유기 설치 (C++)

🔗문제 보러가기

2110번: 공유기 설치

 

🧑‍💻풀이 과정

등간격으로 설치할 수 있는 가장 큰 간격을 매개변수 탐색으로 구하면 됩니다. 입력 받은 집 위치들을 배열(arr)에 담고, 오름차순으로 정렬해준 뒤에 다음 과정을 진행해 주었습니다.

1. left = 0 (첫 번째 ~ 첫 번째 공유기 사이의 범위), right = arr[N - 1] (첫 번째 ~ 마지막 공유기 사이의 범위)
2. mid = (left + right) / 2로 중간 범위값을 구하고, 현재 위치값(currentPos) = arr[0]로 초기화 해줍니다.
3. 공유기 설치 개수를 셀 변수(routerCount)를 1로 초기화합니다. (맨 처음에 하나 설치하고 시작하므로)
4. arr[1] ~ arr[N - 1]까지 순회하며, arr[i] - currentPos >= mid라면, routerCount++
   • 그리고 currentPos = arr[i]로 하여 위치값을 갱신해줍니다.
5. 4번 루프가 끝난 후 routerCount < C라면, 간격이 너무 넓다는 뜻이므로 right = mid - 1을 하여 다시 2 ~ 4번 반복
6. routerCount >= C라면, 좀 더 작은 간격이 있을 수 있으므로 left = mid + 1을 하여 다시 2 ~ 4번 반복
7. left <= right를 만족할 때까지 위 과정을 반복

 

✏️소스 코드 및 결과

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

int FindMaxDistance(const vector<int>& positions, const int N, const int C)
{
	int left = 0, right = positions.back() - positions.front();
	int distance = 1;

	while (left <= right)
	{
		int routerCount = 1;
		int range = (right + left) / 2;
		int currentPosition = positions.front();

		for (int i = 1; i < N; i++)
		{
			if (positions[i] - currentPosition >= range)
			{
				routerCount++;
				currentPosition = positions[i];
			}
		}
			
		if (routerCount < C)
			right = range - 1;
		else
		{
			left = range + 1;
			distance = range;
		}
	}

	return distance;
}

int main()
{
	FAST_IO
	int N, C;
	cin >> N >> C;

	vector<int> positions(N);
	for (int i = 0; i < N; i++)
		cin >> positions[i];

	sort(positions.begin(), positions.end());
	cout << FindMaxDistance(positions, N, C);
	return 0;
}