BOJ 1477 - 휴게소 세우기

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

 

접근

휴게소 간 거리가 최소가 되는 거리를 찾는 문제이다.

최소 거리를 찾는 문제이므로 매개변수 탐색을 통해 해결할 수 있다.

 

무엇을 기준으로 이분적으로 구분을 하면될까?

휴게소 사이 (+ 시작지점과 끝지점 포함)에 새로운 휴게소를 건설한다는 가정하에 N의 거리를 두고 새로운 휴게소가 지어진다고 가정해보자.

이렇게 되면 우리는 휴게소 사이에 둘 새로운 휴게소를 두는 지점을 이분적으로 탐색하면 된다.

 

예제 1번을 예를 들면

휴게소 사이에서 어떤 거리 D을 기준으로 새로운 휴게소가 세워진다.

 

만약 휴게소 사이를 D으로 나누었을 때, 새롭게 세워진 휴게소가 M개가 넘는다면

D를 늘려야 하므로 left = mid+1을 하면 된다.

 

반대로 새롭게 세워진 휴게소가 M개보다 작거나 같으면

D를 줄이면서 최소의 거리를 구하면 된다. (right = mid-1)

 

그런데 왜 새로 세워진 휴게소가 M개 일때도 멈추지 않고 진행될까?

D를 줄여도 M개일 가능성이 존재하기 때문이다.

 

코드

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

using namespace std;

int n, m, l;
int res;
vector<int> v;

int check(int mid) {
	int cnt = 0;
	for (int i = 1; i < v.size(); i++) {
		int dis = v[i] - v[i - 1];
		cnt += (dis / mid);
		if (dis % mid == 0) {
			cnt--;
		}
	}
	return cnt;
}

int main() {
	/*ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);*/
	cin >> n >> m >> l;
	v.push_back(0);
	v.push_back(l);
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		v.push_back(tmp);
	}

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

	int left = 1;
	int right = l;
	while (left <= right) {
		int mid = (left + right) / 2;
		int cnt = check(mid);

		if (cnt > m) {
			left = mid + 1;
		}
		else {
			res = mid;
			right = mid - 1;
		}
	}
	cout << res;
}