[C++] 백준 1477번: 휴게소 세우기

www.acmicpc.net/problem/1477

1477번: 휴게소 세우기

이분 탐색 문제를 몇개 풀어본 지라 나름 자신있게 도전을 했었다.

 

근데 우선 순위 큐를 사용해서 풀 수도 있을 것 같아 계속 하다보니 도저히 답을 구할 수 없었다.

 

그래서 결국 이분 탐색으로 풀려하는데 풀이법이 생각이 안나 다른 사람의 풀이를 결국 참고했다ㅠㅠ

 

예전에 풀었던 입국심사 문제와 조금 비슷한 면이 있는 문제 였는데 너무 생각없이 문제를 접근했던 것 같다.

 

다음 부턴 문제를 풀고 나서 확실히 이해하고 기억하는 습관을 길러야겠다

 

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

vector<int> v;

int main() {
	int n, m, l, x;
	cin >> n >> m >> l;
	v.push_back(0);
	for (int i = 0; i < n; i++) {
		cin >> x;
		v.push_back(x);
	}
	sort(v.begin(), v.end());
	v.push_back(l);
	
	int left = 1;
	int right = l - 1;
	int mid = 0;
	while (left <= right) {
		mid = (left + right) / 2;
		int store = 0;
		for (int i = 1; i < v.size(); i++) {
			int d = v[i] - v[i - 1];
			store += d / mid;
			if (d % mid == 0) {
				store--;
			}
		}
		if (store > m) {
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}

	cout << left;
	return 0;
}

참고한 블로그: paris-in-the-rain.tistory.com/44

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

딱 깔끔하게 푸셔서 도움이 많이 되었다..