Baekjoon 2110 공유기 설치

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

소스결과 2576 KB / 20 ms

출처 Baekjoon 

언어 C++ 17

분류 이분탐색

 

설명

도현이가 언제나 와이파이를 즐기기 위해 공유기 C개를 설치하려고 할때 인접한 공유기 사이의 거리를 가능한 크게 해서 설치 하려한다. 그 때 최대 값을 출력해주자

 

문제가 이해가 안간다.

코드를 봐도 모르겠다.

스터디에서 코드를 받고 코드를 보고 이해하려 했으나. 문제가 더 이해가 안되는 상황에 이르렀다. 공유기 개수.. 공유기 범위는 제한이 없는건가..?

문제 친절하게 설명해주실 분을 구합니다..

 

소스코드

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

using namespace std;

const int MAX = 200000;

bool exist[MAX + 1];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n, c;
	cin >> n >> c;

	vector<int> v(n);
	for (int i = 0; i < n; i++)
		cin >> v[i];

	sort(v.begin(), v.end());

	int left = 0, right = 1000000003;

	while (left <= right)
	{
		int cleft = c - 2;
		int cc = 0;
		int m = (left + right) / 2;

		for (int i = 0; i < n - 1; i++)
		{
			int d = v[i + 1] - v[i];
			if (cc + d <= m)
				cc += d;
			else
			{
				cleft--;
				cc = 0;
			}
		}

		if (cleft >= 0) right = m - 1;
		else
			left = m + 1;
	}

	cout << left;

	return 0;
}