[백준] 1477-휴게소 세우기(C++)

문제링크: https://www.acmicpc.net/problem/1477

1477번: 휴게소 세우기

 

이분탐색임을 인지했는데, 어떻게 풀어나가야 할지 고민했던 문제

 

처음에는 간격이 제일 넓은 구획을 찾고, 그 두 간격을 반토막씩 자르면 어떨까 생각함

하지만 아래 처럼 휴게소가 배치되어있고, m = 2인 경우라면 

 

이렇게 추가가 되어짐...

 

당연히 오답.. 

 

 

 

거리가 비례하게끔, 아래 그림처럼 구성이 되어져야함 

 

 

고민하다가 "거리"로 이분 탐색해야 한다는 것을 깨닫게 됨.

 

 

 

접근방식

 

1. 위 설명처럼 거리를 통한 이분탐색을 생각하게 됨

2. 이분탐색에서의 조건은 휴게소 간격들 사이 해당 거리(mid) 만큼 지정했을 때, 배치 가능한 갯수 

 

 

문제풀이 

 

주석을 자세하게 적어 놓아기 때문에 생략

 

정답 코드입니다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, l;
vector <int> vec;

bool cmp(int& a, int& b) { // 없어도 되지만 간만에 짜보고 싶었어요ㅋㅋ
	if (a < b)
		return true;
	return false;
}

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

	cin >> n >> m >> l;
	int temp;
	vec.push_back(0), vec.push_back(l); //시작점과 끝점 추가 + 이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에도 휴게소를 세울 수 없다. 라는 조건 때문에
	for (int i = 0; i < n; i++) {
		cin >> temp;
		vec.push_back(temp);
	}
	sort(vec.begin(), vec.end(), cmp);



	int low = 0, high = l;
	int mid, result = 0;

	while (low <= high) {
		mid = (low + high) / 2; 

		int val = 0; // 휴게소 사이에 배치 될 수있는 휴게소의 갯수
		for (int i = 1; i < vec.size(); i++) {
			int dist = vec[i] - vec[i - 1]; // 휴게소 a와 b 사이에 간격

			val += (dist / mid); // 휴게소 간격 / 현재 길이
			if (dist%mid == 0) //휴게소가 이미 있는 위치라면 
				val--; // 갯수를 하나 감소 시켜주어야지. 
		}
		if (val > m)  // 배치할 수 있는 휴게소가 m개 보다 많으면
			low = mid + 1; // 길이를 늘려주어 m개가 배치 되게끔 만들어주고 
		else {// 배치될 휴게소가 m개보다 작거나 같을 때 
			high = mid - 1;// 길이(mid)가 더 작아질 수 있을지 확인해야지  
			result = mid;  //결과값을 갱신해주기 
		}
	}

	cout << result << endl;

	return 0;
}