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

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

1477번: 휴게소 세우기

1. 주의할 점

- 시작지점과 끝지점(고속도로의 길이)도 포함해야한다.

- 이분탐색으로 해결한다.

 

2. 구현

- 첫 번째 구현방법: 구간과 구간사이의 길이를 구해서 우선순위큐에 적재한다. 

우선순위큐의 Top에 있는 원소를 뽑아서 반으로 나누고 다시 우선순위큐에 적재한다.

위의 방법을 M번 반복한다.

위의 방법으로 구현을 하면 구간의 거리가 최소가 되지않는다.

Ex) 0 300 500, 휴게소 3개 설치

-> 0 150 300 500

-> 0 150 300 400 500

-> 0 75 150 300 400 500

-> 답: 150

하지만 휴게소를 0 100 200 300 400 500으로 설치한다면 정답은 100이 된다.

 

- 두 번째 구현방법: 이분탐색을 통해 거리 Dist내로 휴게소가 있는지 확인한다.

구간과 구간사이의 거리를 D라고 가정

D/Dist의 몫만큼 Cnt를 추가하고, 만약 D%Dist가 0이면 몫-1만큼 추가한다.

Cnt <= M : 휴게소 Cnt개를 추가 설치해서 각 휴게소의 거리가 Dist보다 작거나 같다.

Cnt > M: 휴게소 M개로 각 휴게소의 거리가 Dist보다 작거나 같게 만들 수 없다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int num, add, maxi, val;
vector<int> v;

bool start(int dist) {
	int cnt = 0;
	for (int i = 0; i < v.size() - 1; i++) {
		int d = v[i + 1] - v[i];
		int val;
		if (d / dist > 0) {
			if (d%dist == 0)	val = (d / dist) - 1;
			else val = (d / dist);
			cnt += val;
		}
	}
	if (cnt <= add) return true;
	return false;
}

int main() {
	cin >> num >> add >> maxi;
	v.push_back(0);
	for (int i = 0; i < num; i++) {
		cin >> val;
		v.push_back(val);
	}
	v.push_back(maxi);
	sort(v.begin(), v.end());
	int low = 1, high = maxi, mid, result;
	while (low<=high) {
		mid = low + (high - low) / 2;
		if (start(mid)) {
			high = mid - 1;
			result = mid;
		}
		else	low = mid + 1;
	}
	cout << result;
	system("pause");
	return 0;
}