문제 : 백준 1477 휴게소 세우기

❓ 문제 설명

✏️ 문제 요약

• 예시는 고속도로의 길이가 1000일 때 200, 701, 800 위치에 휴게소가 있는 상황에서 휴게소를 1개 더 지어야야 합니다.
  단, 고속도로의 끝에는 휴게소를 지을 수 없고 주어진 M개 만큼은 다 지어야 합니다.

• 이 고속도로를 달릴 때, 휴게소가 없는 구간은 0~200, 200~701, 701~800, 800~1000 총 4구간이 있습니다.
  여기서 구간의 최댓값은 200~701 구간인 501 입니다.

• 위치 500에 휴게소를 지으면 이때 휴게소가 없는 구간의 최댓값은 300이 됩니다. 1개를 모두 설치했고 조건을 만족했지만 저희가 문제에서 구해야하는 답은 조건을 만족하는 휴게소가 없는 구간의 최댓값 중 최솟값을 구해야 합니다!
  즉, 최댓값이 300보다 작지만 조건을 모두 만족하는 값이 있는지 확인을 해야 합니다.

• 이번에는 위치 451에 휴게소를 지으면 이때 휴게소가 없는 구간의 최댓값은 251이 됩니다. 앞서 구한 300보다 작고 조건을 모두 만족했으므로 300보다 정답에 더 근접한 답입니다.

• 추가 휴게소의 위치를 451 보다 줄여나가봐도 251보다 더 작은 구간의 최댓값이 존재하지 않으므로 답은 251이 됩니다.

🎯 문제 해결 방법

• 이 문제는 구간이 정해져있고 답을 만족하는 최솟값을 찾는 문제이므로 이분 탐색으로 풀어보았습니다.

vector<int> v;
...
v.push_back(0); //시작 점, 끝 점과 휴게소의 거리도 구해줘야하기 때문에 넣어줍니다.
v.push_back(l); //l은 고속도로의 길이

for(int i=0; i<n; i++){
	int x; cin >> x;
	v.push_back(x);
}
sort(v.begin(), v.end());

• 휴게소들의 위치 정보를 받을 vector를 선언

• 휴게소들의 위치 정보를 받고 이분 탐색을 위해 정렬해줍니다.
  이분 탐색은 반드시 정렬된 배열에서 사용해야 합니다!!!

int st = 1, en = l;
int mid,ret=0;
while(st <= en){
	mid = (st + en) / 2;
	if(chk(mid)){
		st = mid + 1;
	}else{
		ret = mid;
		en = mid - 1;
	}
}

• 시작 위치 : 1, 끝 위치 : L (소문자로 쓰면 잘 안보여서... 대문자로 썼습니다..)
  여기서 mid의 값은 휴게소가 없는 구간의 최댓값을 나타냅니다.

• mid의 값이 while문을 계속해서 돌면서 최소가 될 때 까지 결과를 출력할 ret 변수를 갱신해줍니다.

bool chk(int mid){
	int cnt = 0;
	for(int i=1; i<v.size(); i++){
		int dist = v[i] - v[i-1]; //휴게소 끼리의 거리
		cnt += dist / mid; //dist를 mid로 나눴을 때 들어갈 수 있는 휴게소의 갯수
		if(dist % mid == 0){ 
			cnt--; //이미 휴게소가 있는 위치에는 휴게소를 지을 수 없으므로 1개 빼줍니다.
		}
	}
	return cnt > m; //모든 구간을 확인했을 때 지을 수 있는 휴게소가 m개 보다 많다면 true를 반환합니다.
}

• 휴게소가 없는 구간 값(mid)을 chk함수로 확인했을 때 지을 수 있는 휴게소의 갯수가 m개보다 많으면 true를 반환하고 st = mid + 1을 하게 됩니다.
  즉, 휴게소를 m개 보다 더 많이 지을 수 있으면 mid의 값을 늘려서 m개 만큼 짓기 위함입니다.

• 지을 수 있는 휴게소의 갯수가 m개보다 작거나 같으면 false를 반환하고 en = mid - 1을 하게 됩니다.
  즉, 휴게소를 m개 보다 더 지을 수 있도록 mid의 값을 줄여서 m개 만큼 짓기 위함입니다.

💻 전체 코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,m,l;
vector<int> v;
bool chk(int mid){
	int cnt = 0;
	for(int i=1; i<v.size(); i++){
		int dist = v[i] - v[i-1];
		cnt += dist / mid;
		if(dist % mid == 0){
			cnt--;
		}
	}
	return cnt > m;
}
int main(void){
	ios_base::sync_with_stdio(0);
	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 x; cin >> x;
		v.push_back(x);
	}
	sort(v.begin(), v.end());
	
	int st = 1, en = l;
	int mid,ret=0;
	while(st <= en){
		mid = (st + en) / 2;
		if(chk(mid)){
			st = mid + 1;
		}else{
			ret = mid;
			en = mid - 1;
		}
	}
	
	cout << ret;
	return 0;
}

😊 결과

런타임 에러 (DivisionByZero)가 발생한 이유

int st = 0, en = l;
	int mid,ret=0;
	while(st <= en){
		mid = (st + en) / 2;
		if(chk(mid)){
			st = mid + 1;
		}else{
			ret = mid;
			en = mid - 1;
		}
	}

• 시작 점을 0, 끝 점을 L로 잡아서 에러가 발생했습니다.
• 만약, 시작 점이 0이고 L의 값이 1이면 (0 + 1) / 2 연산을 통해 mid의 값이 0이 됩니다.

if(dist % mid == 0){
	cnt--;
}

• chk 함수 dist % mid == 0 이 부분에서 dist를 0으로 나머지 연산을 했기 때문에 에러가 발생했습니다.
• 해결 방법은 시작 점을 0이 아닌 1로 주면 됩니다.
  int st = 1, en = l