[백준/BOJ] 백준 18877번 : Social Distancing

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

18877번: Social Distancing

 

소들 사이 거리를 특정값 이상으로 해서 주어진 범위에 모두 배치할 수 있는지 확인하는 이분 탐색을 수행하여, 매개 변수 탐색을 통해 문제를 해결했다.

 

코드

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

int n, m;
vector<pair<long long, long long>> range;

//소들 사이 거리를 d 이상으로 해서 모두 배치할 수 있는지 확인
bool check(long long d) {

	long long remain = n; //배치해야될 소의 수
	long long point = 0; //현재 소를 배치할 수 있는 최소 위치

	for (int i = 0; i < range.size(); i++) {
		long long range_left = range[i].first;
		long long range_right = range[i].second;

		range_left = max(range_left, point);

		if (range_left > range_right) {
			continue;
		}

		//range_left ~ range_right 범위 사이에 배치할 수 있는 만큼 소를 배치
		long long add = ((range_right - range_left) / d) + 1;
		remain -= add;

		point = range_left + (add * d);

		if (remain <= 0) {
			break;
		}
	}

	if (remain <= 0) {
		return true;
	}

	return false;
}

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

	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		long long a, b;
		cin >> a >> b;
		range.push_back(make_pair(a, b));
	}
	sort(range.begin(), range.end());

	long long left = 0;
	long long right = 1000000000000000001;
	long long result = -1;
	while (left <= right) {
		long long mid = (left + right) / 2;

		if (check(mid)) {
			result = mid;
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}

	cout << result;

	return 0;
}