백준 1477번 휴게소 세우기 (C++)

 이번에 이분탐색을 열심히 풀어보고 있다.

이 문제는 언뜻보면 DP인가 싶기도 하다. 만약 이 문제를 이분 탐색이라는 키워드를 못보고 풀었다면 아마 이분탐색이라는 것을 알아차리기까지 오랜 시간이 걸렸을 것 같다. 

 

풀이는 다음과 같다.

1. 먼저 새워져있는 휴게소들을 정렬한다.

2. 정렬된 휴게소들 간의 거리를 저장해둔다.

3. 이분탐색으로 lo = 0 hi = L 로 정한다.

4. 갱신조건은 휴게소 간의 거리를 mid로 나눈 값을 보는 것이다. 만약 mid로 나누어 떨어지면 휴게소가 100, 200에 새워져있다고 하자. 그런데 mid가 50이면 150 지점에 한개만 새우면 되는데 2개를 새울 것이다. 이 경우를 방지하기 위해 나누어 떨어질 경우는 휴게소를 한개 지워준다.

5. 만약 휴게소를 M만큼 지었거나 숫자가 남을 경우는 가능하니 answer를 갱신한다.

5. 파라메트리 방법으로 끝까지 반복한다. 

 

여기서 처음에 while(lo <= hi) hi = L, lo = 1 이라면 정답이다. 그러나 while(lo + 1 < hi ) 라면 hi = L, lo = 0 으로 해야한다. 어라? 그러나 문제 조건에서 0과 L에는 설치하지 않는다고 했다. 그런데 왜 이 것들이 정답일까?

 

바로 lo + 1 < hi 는 lo < mid < L 이 보장되기 때문이다. 

lo = 0 hi = 0 까지 도달해버렸다면 while 조건으로 인해 0은 실행되지 않는다. hi의 경우에도 마찬가지.

 

그렇다면 lo <= hi 의 경우에는? lo == hi 일 때 lo = 0 일때도 실행되어버린다. 때문에 lo는 1부터 시작하는 것이다. 

 

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

int N, M, L;
vector<int> shelter;

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

	cin >> N >> M >> L;
	
	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;
		shelter.push_back(tmp);
	}
	shelter.push_back(0);
	shelter.push_back(L);
	sort(shelter.begin(), shelter.end());
	int high = -1;
	vector<int> leng;
	for (int i = 1; i < shelter.size(); i++) {
		leng.push_back(shelter[i] - shelter[i - 1]);
		//cout << shelter[i] - shelter[i - 1] << endl;
	}
	//for (auto a : leng)
	//	cout << a << " ";
	//cout << endl;
	int hi = L;
	int lo = 0;
	int answer = 0;
	while (lo + 1 < hi) {
		int mid = (hi + lo) / 2;
		int ch = M;
		for (int i = 0; i < leng.size(); i++) {
			if (leng[i] % mid == 0){
			ch = ch - leng[i] / mid;
            ch++;
            }else{
                ch = ch - leng[i] / mid;
            }
		}
		if (ch >= 0) { // 0이상이면 가능함
			answer = mid;
			hi = mid;
		}
		else
			lo = mid;
	}

	cout << answer << '\n';

	return 0;
}