백준 17266번: 어두운 굴다리 (C++)

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

17266번: 어두운 굴다리

 

풀이

전형적인 이분 탐색 문제. 

는 모르겠고 이분 탐색 풀고 싶어서 풀어봤다.

 

이분 탐색 조건인 is_possible 함수 설정을 조금 생각해야했다. 

mid (가로등 높이) 값을 비교해야하는 부분이

 

1. 0 ~ 첫 가로등

2. 가로등 사이

3. 마지막 가로등 ~ N

 

이렇게 존재하는데

가로등 사이는 양 쪽에서 빛을 비추기 때문에 반으로 나눠주었다.

 

3가지 조건을 매번 탐색하며 진행했는데

쓰면서 보니 가장 긴 거리보다 큰 mid 값을 이용하는 방법이 더 효율적일 것 같다...

 

이분 탐색임을 알고 풀었는데 실제로 이런 문제들 코테에서 이분 탐색인지 바로 알 수 있을 지가 문제다..

 

 

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M;
vector<int> x;

bool is_possible(int mid) {
	if (x[0] - 0 > mid || N - x[x.size() - 1] > mid) return false;
	for (int i = 0; i < x.size() - 1; i++) {
		if ((x[i + 1] - x[i]) > mid * 2) return false;
	}
	return true;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int a;
		cin >> a;
		x.push_back(a);
	}

	int left = 0, right = 1e9 + 2, ret = -1;

	while (left <= right) {
		int mid = (left + right) / 2;

		if (is_possible(mid)) {
			ret = mid;
			right = mid - 1;
		}
		else left = mid + 1;
	}
	cout << ret;
}