[백준 알고리즘 c++] 문제 34.공유기 2110

알고리즘

 

[문제]

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

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

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

[소스 코드]

#include <iostream>
#include <algorithm>

using namespace std;

int N, C;
int x[200000];

int main()
{

	//
	// 문제
	// 1. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 
	//		최대로 하는 프로그램을 작성하시오.
	// 입력
	// 1. 집의 개수 N과 공유기 개수 C를 입력 받는다. (나눗셈 사용)
	// 처리
	// 2. 공유기 개수만큼 
	// 출력
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	//1.집의 개수와 공유기의 개수를 입력 받는다.
	cin >> N >> C;

	//2. 집의 좌표를 입력 받는다.
	for (int i = 0; i < N; i++)
	{
		cin >> x[i];
	}

	//3. 공유기 사이의 거리를 구하기 위해 집의 좌표를 정렬한다.
	sort(x, x + N);
	
	//4.이진 검색을 할 범위는 가장 인접한 공유기 사이의 거리
	// [1, x[N - 1]] (최소 거리 1, 최대 거리 x[N - 1])
	int s = 1; // 0 ~ 1 , 1 ~ 2
	int e = x[N - 1] + 1; // 0 ~ 9
	int result = 0;

	while (s < e)
	{
		// 4-1. 중앙값을 해의 후보로 정한다.
		//s : 1, e : 10, m : 5
		int m = (s + e) / 2; //공유기 거리


		//4-2. 실제로 m거리 만큼 떨어뜨려 몇개의 공유기를 배치할수 있는지 확인한다.
		int count = 1;
		int distance = x[0] + m;
		
		for (int i = 0; i < N; i++)
		{
			if (distance <= x[i])
			{
				distance = x[i] + m;
				count++;
			}
		}


		if (count >= C)
		{
			//4-3. 최대 길이 최신화
			if (result < m)
			{
				result = m;
			}

			//4-4. 더 찾을수 있는지 범위 조절
			s = m + 1;
		}
		else
		{
			e = m;
		}


	}


	//4. 최대 거리를 출력한다.
	cout << result;

}

 

[피드백]