[C/C++] 백준 - 17266번 : 어두운 굴다리

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

17266번: 어두운 굴다리

이분 탐색을 이용해서 해결해야 하는 문제이다.

처음 가로등과 마지막 가로등을 제외하면 가로등끼리 떨어진 거리가 존재한다. 그 거리를 비교값으로 설정해

(내가 임의로 지정한 길이 * 2)보다 가로등 사이 걸이가 길다면 가로등 사이 밝히지 못하는 구간이 존재한다는 의미이다.

위 방법으로 이분 탐색을 진행해주면된다. 그리고 처음 가로등은 (내가 임의로 지정한 길이)보다 좌표값이 더 큰 곳에 위치한다면 처음 가로등에서 0의 위치까지 밝히지 못하는 구간이 존재한다는 의미이며, N - 마지막 가로등 위치 길이가 내가 정한 임의의 거리보다 크다면 마지막 구간을 밝히지 못한다는 뜻이다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <set>
#include <unordered_set>
#include <map> 
#include <algorithm>
#include <cmath>
#define CUNLINK ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long
#define INF 987654321
#define Mod 10007
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int pos[100001];

int main() {
	CUNLINK;
	int N, M;
	cin >> N;
	cin >> M;
	for (int i = 0; i < M; i++) cin >> pos[i]; 
	int answer = INF;
	int pl = 0, pr = 100000;
	while (pl <= pr) {
		int mid = (pl + pr) / 2;

		bool isCan = true;
		if (pos[0] > mid) isCan = false;
		for (int i = 0; i < M-1; i++) {
			if (pos[i + 1] - pos[i] > mid*2) {
				isCan = false;
				break;
			}
		}
		if (N - pos[M - 1] > mid) isCan = false;

		if (!isCan) pl = mid + 1;
		else {
			answer = min(answer, mid);
			pr = mid - 1;
		}
	}
	cout << answer;

	return 0;
}