[BOJ 백준] 1477 - 휴게소 세우기

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

1477번: 휴게소 세우기

 

이분탐색을 활용하는 문제였다. 단순히 이분탐색 뿐 아니라 파라메트릭 서치를 사용하여야 한다. 물론 이 문제는 N의 값이 작아서, 이분탐색을 활용하지 않아도 된다.

 

문제는 현재 세워진 휴게소들 사이에 M개의 휴게소를 세우고 휴게소가 없는 구간의 최댓값의 최솟값을 출력하는 것이다.

 

즉 최대한 촘촘히 휴게소를 세워서, 두 휴게소의 거리 중 가장 멀리 떨어진 거리가 최소가 되게 하라는 것이다.

 

이분탐색이 어떻게 진행되는지 알고 있다면, 어떤 값을 left, right, mid로 설정해야할지를 정해야 한다. 이 부분이 가장 어렵다. 

 

답은, "거리"로 접근을 하면된다.

 

새로 지어질 휴게소는 이미 만들어진 휴게소들 사이사이에 들어간다.

 

문제에 나온 예시처럼 {200,701,800}의 위치에 휴게소가 세워져있고, 도로의 길이가 1000이라 하면

 

새로 지어질 휴게소는

1. 1~199
2. 201~700 
3. 702~799
4. 801~999

중 아무곳이나 들어갈 수 있다. 이때 중요한 점이자 문제를 푸는 방법의 핵심은

 

1번의 범위에 꼭 1개의 휴게소가 들어갈 필요는 없다는 것이다.

 

만약 새로 지어지는 휴게소 사이의 거리를 50으로 잡으면 1번의 범위에는 {50, 100, 150} 총 3개의 휴게소가 들어갈 수 있을 것이다.

 

이렇게, 이미 존재하는 휴게소 사이사이에 일정한 거리를 두고 휴게소를 세웠을 때, 세운 휴게소의 개수가 문제에 주어진 m값과 같으면 된다. 

 

 

소스코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
#define endl "\n"
using namespace std;
int n, m, l;

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m >> l;
	vector<int>store;
	int pos;
	store.push_back(0); // 거리의 시작지점
	for (int i = 0; i < n; i++) {
		cin >> pos;
		store.push_back(pos);
	}
	store.push_back(l); // 거리의 끝지점
	sort(store.begin(), store.end());
	
	int left = 1;
	int right = l - 1;
	int mid = 0;
	while (left <= right) {
		mid = (left + right) / 2; // 기존 편의점에서 새롭게 세울 편의점 사이의 거리 
		int new_store = 0;
		for (int i = 1; i < store.size(); i++) {
			int dist = store[i] - store[i - 1]; 
			new_store += (dist / mid); // 두 편의점 사이에 세울 수 있는 편의점의 개수
			if (dist % mid == 0) { // 나누어 떨어지는 경우 : 편의점이 겹쳐서 세워지므로 1을 뺌
				new_store--;
			}
		}
		
		if (new_store > m) { // 세워야할 편의점 보다 더 많이 생김 -> 간격을 늘림
			left = mid + 1;
		}
		else { // 세워야할 편의점 보다 더 적게 생김 -> 간격을 줄임
			right = mid - 1;
		}		
	}
	
	cout << left;
	return 0;
}