[알고리즘] 백준 3020번: 개똥벌레 (C++), 다시 한 번 틀을 깨다

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

3020번: 개똥벌레

 

이분 탐색이라는 문제를 알고서 풀었기 때문에 어느 타이밍에 이분 탐색이 나와야 할지 감을 잡지 못했다.

첫 번째로 떠오른 방법은

1) 입력을 받을 때, 종유석과 석순으로 나누어서 석순이면 밑에서부터 장애물이 하나씩 추가되는 것이기 때문에 1 ~ 입력값까지 +1을 해주고, 종유석이면 위에서부터 밑으로 +1을 해주었다.

2) 각 구간 별로 부숴야 할 장애물들이 저장되어있기 때문에 정렬을 하고, 맨 앞에 있는 부숴야 하는 장애물 값이 최소가 되기 때문에 upper_bound와 lower_bound를 사용하여 최솟값을 갖는 구간이 몇 개인지 cnt로 파악하였다.

>> 시간 초과 발생

 

이유는 1번에서 일어난다.

더 정확하게 말하면 애초에 입력을 받을 때부터 문제가 발생한다. n이 200,000까지인데 높이가 500,000을 가지는 종유석 혹은 석순이 들어오면 시간 복잡도가 O(200,000 * 500,000)로 나와서 시간 초과가 당연하다.

>> '당연히 입력에서는 시간 초과가 발생하지 않겠지'라는 무의식적인 편협한 생각에 의해 도출된 오류다.

 

[TLE 코드]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 8% 까지만 감 >> 시간 초과
int n, h;

int main() {
	cin >> n >> h;
	vector<int> bugRoad(h + 1, 0);

	int idx;
	for (int i = 0; i < n; i++) { // 200,000
		cin >> idx;
		if (i % 2 == 0) {
			for (int j = 1; j <= idx; j++) {
				bugRoad[j] += 1;
			}
		}
		else {
			for (int j = h; j > h - idx; j--) {
				bugRoad[j] += 1;
			}
		}
	}
    // 입력에서 최악의 경우에는 200,000 * 500,000까지 나올 수 있다.
	
    sort(bugRoad.begin(), bugRoad.end());

	cout << bugRoad[1] << ' ';
	
	int low = lower_bound(bugRoad.begin(), bugRoad.end(), bugRoad[1]) - bugRoad.begin();
	int high = upper_bound(bugRoad.begin(), bugRoad.end(), bugRoad[1]) - bugRoad.begin();
	int cnt = high - low;

	cout << cnt;

	return 0;
}

---

솔루션

그렇다면 입력을 받을 때는 어떠한 기능을 수행하지 않고, 입력을 받게 해주어야 한다. 그렇다면 어떻게 풀 수 있을까?

(+참고 https://jaimemin.tistory.com/1109)

 

참고했던 곳에서는 다음과 같은 솔루션을 제공한다.

 

1) 종유석과 석순을 따로 입력받게끔 따로 배열을 선언한다.

 

2) 두 배열 정렬 (구간 이분 탐색을 위해)

 

3) 각 구간에서 최솟값과 그 개수를 찾는 것이 이번 문제의 목표다.

>> 즉, 각 구간에서 맞는 장애물의 개수를 구하는 것이 목표다.

 

4) 각 구간별 탐색을 위해 for문을 돌린다.

 

5) 지금 for문 안에서 현재의 높이가 i라고 한다면, 정렬되어있는 석순에서 높이가 i인 석순이 나올 때의 위치를 반환한 값은 그 위치부터는 i에게 모든 석순이 장애물이라는 뜻이므로 석순 배열의 사이즈에서 그 위치 값을 빼준다.

>> lower_bound 유도

>> 이유 높이가 i - 1인 i구간에서 개똥벌레에게 장애물이 되지 않는다.

>> i보다 크거나 같은 높이의 석순만이 개똥벌레에게 장애물이 된다.

 

6) 종유석은 위에서 자라므로 높이 h에서 구간의 높이(i)를 빼준 값보다 큰 값들이 i에게 있어서 장애물이 된다.

>> upper_bound 유도

 

종유석과 석순으로부터 구한 값이 i 구간에서 맞는 장애물의 개수가 된다.

 

---

그렇다면 왜 이분 탐색을 필요로 할까?

이유는 첫 시도에 틀렸던 이유와 비슷하다.

이분 탐색을 쓰지 않았다면, 현재 구간의 높이 i가 1이라고 가정하자.

석순 배열에서 1보다 크거나 같은 값들을 하나하나 찾아야 한다. (완전 탐색)

종유석 배열에서는 h - 1보다 큰 값들을 하나하나 찾아야 한다. (완전 탐색)

 

이러한 구간의 크기가 500,000이 최대로 주어질 수 있으며 종유석과 석순을 둘로 나누었다고 한들

O(500,000 * (200,000 / 2 + 200,000 / 2))으로 최대 시간 복잡도가 잡힐 수 있기 때문에

석순과 종유석을 정렬한 뒤 upper_bound와 lower_bound를 사용하여 보다 빠르게 탐색해야 한다.

 

---

[AC 코드]

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

int n, h;

int main() {
	cin >> n >> h;

	vector<int> bottom, top;
	int value1, value2;
	for (int i = 1; i <= n / 2; i++) {
		cin >> value1 >> value2;
		bottom.push_back(value1); // 석순 저장
		top.push_back(value2); // 종유석 저장
	}

	sort(bottom.begin(), bottom.end());
	sort(top.begin(), top.end());

	int result = INT_MAX;
	int cnt = 1;

	for (int i = 1; i <= h; i++) { // 구간 별로
		int temp = bottom.size() - (lower_bound(bottom.begin(), bottom.end(), i) - bottom.begin());
		temp += top.size() - (upper_bound(top.begin(), top.end(), h - i) - top.begin());

		// 최솟값을 찾는 과정
		// 최솟값이 나오면 result에 할당이 되고,
		// 최솟값이 나올 때만이 cnt++가 된다.
		if (temp == result) {
			cnt++;
		}
		else if (temp < result) {
			result = temp;
			cnt = 1;
		}
		//cout << temp << '\n';
	}

	cout << result << ' ' << cnt << '\n';
	return 0;
}

---

느낀 점

최솟값의 개수를 구하는 과정의 코드가 신기했다. 처음엔 이게 무슨 소리인가 싶었는데 괜찮은 팁인 거 같다.

이번 이분 탐색 문제는 기존의 틀을 다시 한번 깨는 문제였다.

다시 한번 깨닫는 것이

1) 찾으려는 값이 무엇인지

2) 값을 찾을 때, TLE가 발생하는지

3) TLE가 발생할 거 같다면 이분 탐색으로 가능한지

의 절차를 새겨두어야 한다.