[C++][백준] - 개똥벌레 (3020번)

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

3020번: 개똥벌레

🔔 문제 : 

 

아래에서 자라나는 석순과, 위에서 자라나는 종유석이 있는데 길이가 번갈아가면서 주어집니다. 

 

이 길이를 통하여, 최솟값과 구간의 수를 공백으로 구분하여 출력하는 문제입니다.

---

🔔 Kick Point :

 

1번째 부터 n번째 구간까지 장애물을 일일히 구한다면 O(n*h)이 되버려서 정말 많은 수를 구해야 할 것입니다.

 

하지만 구간을 구할 때, 정렬 후 바이너리 서치인 O(lgn * h)을 통해 구하게 된다면 더 빠르게 할 수 있습니다.

 

따라서 Algorithm 헤더의 lower_bound 함수를 사용하여, 종유석이나, 석순에 닿는지 않닿는지를 파악할 수 있습니다.

 

lower_bound () : 어떤 수 이상이거나, 큰 수 인 경우 처음으로 나온 인덱스를 출력해 줍니다.

 

예를 들면 , 석순이 {1, 3, 5} 있다고 하고, 2의 구간을 구하기 위해 lower_bound 넣어보면, 3의 자리에있는 인덱스 1이 나옵니다.

 

이는 1은 2의 구간에서는 장애물이 취급 안 됨을 알 수 있기에, n-1 = 2, 즉 3,5인 2개는 장애물로 부셔짐을 알 수 있습니다.

---

🔔 Code :

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

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

	int n, h;
	int floor[100000];
	int ceil[100000];

	cin >> n >> h;

	for (int i = 0; i < (n/2); i++) {
		cin >> floor[i] >> ceil[i];
	}
	
	sort(floor, floor + (n/2));
	sort(ceil, ceil + (n/2));

	int result(987654), cnt(1);

	// O(lg n) lower_bound, upper_bound
	for (int i = 1; i <= h; i++) {
		
		int tmp(0);
		// i번째 겹치는 석순
		tmp += lower_bound(floor, floor + (n/2), i) - floor;
		tmp += lower_bound(ceil, ceil + (n / 2), h - i +1) - ceil;
		tmp = n - tmp;
		
		if (result > tmp) {
			cnt = 1;
			result = tmp;
		}
		else if (result == tmp) {
			cnt++;
		}
	}
	cout << result << ' ' << cnt;

}

---