1. 문제설명

0~N의 길이 주어진다.
가로등의 개수 M은 위치 x들에 놓인다.
가로등의 높이를 모두 같은 값으로 설정할 때,
굴다리를 전부 비추는 높이를 구하라

2. 알고리즘 설계

어떤 숫자를 구한다? ==> 이분탐색
이 문제의 모호함은 다음과 같다.
- 10, 2, 0 9 가 입력으로 들어왔다고 가정해보자.
  - 나는 처음에 답이 4라고 생각했다.
    - 0번 위치의 가로등이 0~4 구간을 비추고,
    - 9번 위치의 가로등이 5~10까지 비추고 있다.
  - 그러나, 답은 5여야 한다.
    - 4~5구간이 어둡기 때문이다.
    - 즉, 양 끝이 아니라면, 4, 5로 끝나는 게 아니라
    - 0번 위치는 5, 9번 위치는 4까지 비춰야 전부 비추는 것이다.
- 이 반례가 없었다면 못 풀었다…

3. 로직

이분 탐색에서 중요한 건 left, right 값을 지정하는 것이다.
left=1, right=n으로 설정한다.
- 사실 최대 값인 100,000으로 해도 상관없다.
compare를 0부터 시작해서,
가로등이 비추는 왼쪽 처음 위치가 compare보다 작은지 검사한다.
compare보다 크다면, 비추지 못하고 있는 것이다.

4. 전체 코드

#include<bits/stdc++.h>
using namespace std;

int n, m, light[100000];

bool check(int h) {
	int cmp = 0;

	for (int i = 0; i < m; i++) {
		if (light[i] - h <= cmp) cmp = light[i] + h;
		else break;
	}

	return n - cmp <= 0;
}

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

	cin >> n >> m;
	for (int i = 0; i < m; i++) cin >> light[i];

	int left = 1, right = n, ans = 0;
	
	while (left <= right) {
		int mid = (left + right) / 2;

		if (check(mid)) {
			ans = mid;
			right = mid - 1;
		}
		else left = mid + 1;
	}

	cout << ans;
	return 0;
}

5. 소감

그림을 보면 2. 알고리즘 설계에서 설명한 반례를 떠올릴 수 없었다.
여러 가정을 해보면서, 저런 반례를 직접 찾을 수 있도록 해야겠다.

BOJ 17266. 어두운 굴다리

1. 문제설명

2. 알고리즘 설계

3. 로직

4. 전체 코드

5. 소감