[알고리즘] 백준 17266번: 어두운 굴다리 (C++), 아이디어 능력이 더 좋아지면 좋겠다

평범한 이분 탐색 문제이지만 이번 문제에서 중요했던 포인트가 평소에 내 취약점이라 정리를 해두고 싶었다.

난 기본적으로 범위? 같은 것에 약하다. 혹은 0으로 시작하는지 1로 시작하는지 이런 문제처럼 범위에 영향을 주는 그런 문제들에 좀 약하다.

 

---

내가 짰던 코드의 오류 이유

우선 코드를 짜서 TC는 통과할 수 있지만 제출했을 때는 시간 초과를 유발한다. 그리고, 반례도 있었다.

 

반례의 이유부터 먼저 말하자면 나는 코드를 짤 때, 구간이 아닌 점들로 가로등이 빛을 비추고 있는지 체크했었다.

그러다 보니 4와 5에 빛을 비춘다고 한들 4~5 사이의 구간은 비추지 못하는 것을 알 수 있다.

(코드 블록에 그에 따른 반례도 적어두었다.)

 

시간 초과가 날 거라고는 어느 정도 예상을 했었다. 그래도 구현을 시켜보자가 목적이었다.

while반복문에서 O(logN)으로 최대 범위 log(100,000)

그 안에 for문에서 log(200,000) * 가로등 개수의 최대 범위 (100,000)

또 그 안에 for문에서 높이(mid)가 초기에 50,000으로 주어질 때

전체 시간 복잡도는 아니지만 log(200,000) * (100,000) * (50,000)

단순한 부분 시간 복잡도인데도 50억이 훌쩍 넘는다.

 

그래서 현재의 논리는 적합하지 않다고 생각했다.

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

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

	int n, m;
	cin >> n >> m;
	vector<int> arr; // 가로등
	for (int i = 0; i < m; i++) {
		int idx;
		cin >> idx;
		arr.push_back(idx);
	}

	sort(arr.begin(), arr.end());
	int low = 1;
	int high = n; // 전체를 다 비추는 가로등
	int answer = 0;

	while (low <= high) {
		int mid = (low + high) / 2; // 가로등 높이
		vector<bool> road(n + 1, 0);
		for (int i = 0; i < arr.size(); i++) {
			for (int range = arr[i] - mid; range <= arr[i] + mid; range++) {
				if (range >= road.size()) { // road의 사이즈를 넘어서는 경우
					continue;
				}
				road[range] = 1;
			}
		}

		bool check = 1;
		for (int i = 0; i < road.size(); i++) {
			if (road[i] == 0) {
				check = 0;
			}
		}

		if (check == 1) {
			answer = mid;
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}

	cout << answer;
	return 0;
}
/*
이 반례가 허용되지 않는 이유는
난 점들로 체크했기 때문이다.
4와 5점을 체크할 수는 있지만
4~5 사이의 구간은 체크할 수가 없다.
뿐만 아니라 이 코드는 시간초과를 유발한다.

10
2
0 9
*/

---

솔루션

우선 배열을 사용하지 않아야 한다.

가로등이 비추는 빛이 맞닿아 있거나 서로 겹치면 어두운 부분이 없다.

이 논리를 가지고 범위를 가지고서 이분 탐색을 구현하면 되는 문제다.

각 끝점에서만 한 번 더 들여다보면 보이는 체크해야 할 구간들을 더 체크해주면 된다.

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

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

	int n, m;
	cin >> n >> m;
	vector<int> arr; // 가로등
	for (int i = 0; i < m; i++) {
		int idx;
		cin >> idx;
		arr.push_back(idx);
	}

	sort(arr.begin(), arr.end());
	int low = 1;
	int high = n; // 전체를 다 비추는 가로등
	int answer = 0;

	while (low <= high) {
		int mid = (low + high) / 2; // 가로등 높이
		bool check = 1;
		if (arr[0] - mid > 0) {
			check = 0;
		}
		if (arr[m - 1] + mid < n) {
			check = 0;
		}
		for (int i = 1; i <= m - 1; i++) {
			if (arr[i - 1] + mid < arr[i] - mid) {
				check = 0;
				break;
			}
		}

		if (check == 1) {
			answer = mid;
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}

	cout << answer;
	return 0;
}

---

꼭 이분 탐색을 쓰지 않아도 된다

풀고 나서 든 생각이었다. 각 가로등의 위치들의 차를 가지고 최댓값을 뽑아내도 답이 나오지 않을까라는 생각이 들어 구현해보았다.

유의해야 할 점은 구간의 차이가 홀수일 때는 빛이 곂쳐있게끔 빛을 쏘아야 한다는 생각만 있다면 쉽게 구현할 수 있었다.

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

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

	int n, m;
	cin >> n >> m;
	vector<int> arr; // 가로등
	for (int i = 0; i < m; i++) {
		int idx;
		cin >> idx;
		arr.push_back(idx);
	}

	sort(arr.begin(), arr.end());
	
	int idx = 0;
	int differ = 0;
	for (int i = 0; i < arr.size(); i++) {
		if (i == 0) {
			idx = arr[i];
			continue;
		}
		
		int differ = arr[i] - arr[i - 1];
		if (differ % 2 == 1) {
			differ += 1;
		}
		idx = max(idx, differ / 2);
	}

	idx = max(idx, n - arr.back());
	cout << idx;
	return 0;
}