[BOJ] 3020번 개똥벌레 (C++)

문제 (https://www.acmicpc.net/problem/3020)

3020번: 개똥벌레

문제를 읽고 고민을 하다가.. 예전에 푼 문제에서 lower_bound와 upper_bound를 사용했던 게 생각이 났다. 구현을 해봤지만 시간 초과가 발생했고 구글링으로 약간의 힌트를 얻은 후 구현했다. 

 

석순과 종유석을 각각 입력받고 정렬한다. 정렬 후, 1부터 h까지 반복하며 각 높이일 때 몇 개의 장애물을 파괴하는지를 구한다. 이때 lower_bound를 사용하는 것이다. 장애물의 개수를 구하고 저장할 때 종유석의 경우 반대 방향이므로 변수를 주의해서 넣어주어야 한다.

해당 높이에서 파괴되는 장애물의 개수를 구했으면, 그 개수가 최솟값인지 확인해준다. 최솟값이 갱신되었다면 카운트를 1로 설정해주고, 최솟값과 일치하면 카운트를 증가시켜준다.

---

lower_bound: value 값 보다 크거나 같은 첫 번째 원소의 주소

upper_bound: 처음으로 value 값을 초과하는 원소의 주소

---

[소스코드]

	/*
	BOJ 3020번: 개똥벌레
	DATE: 2022-01-03
	UPDATE: 2022-01-17
	*/
	#include <iostream>
	#include <algorithm>
	#include <vector>
	using namespace std;
	vector<int> down, up;
	int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, h, a, b;
	int min = 500000, cnt = 0;
	cin >> n >> h;
	for(int i = 0 ; i < n / 2; i++) {
	cin >> a >> b;
	down.push_back(a); up.push_back(b);
	}
	sort(down.begin(), down.end());
	sort(up.begin(), up.end());
	vector<int> ans(h);
	for(int i = 1 ; i <= h ; i++) {
	int downIdx = lower_bound(down.begin(), down.end(), i) - down.begin(); // 석순
	int upIdx = lower_bound(up.begin(), up.end(), h - i + 1) - up.begin(); // 종유석
	int cur = n - (downIdx + upIdx); // 높이 i일 때 몇 개의 장애물을 파괴하는지
	if(cur < min) {
	min = cur;
	cnt = 1;
	}
	else if(cur == min) cnt++;
	}
	cout << min << " " << cnt;
	return 0;
	}

view raw 3020.cpp hosted with ❤ by GitHub

 

[시간초과 소스코드]

	/*
	BOJ 3020번: 개똥벌레
	시간초과
	*/
	#include <iostream>
	#include <algorithm>
	using namespace std;
	int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, h, num;
	int start, end, sum;
	int min = 500000;
	cin >> n >> h;
	int arr[h] = {0,};
	for(int i = 0 ; i < n ; i++) {
	cin >> num;
	if((i + 1) % 2 != 0) { //석순
	for(int j = 0 ; j < num ; j++) arr[j]++;
	}
	else{ //종유석
	for(int j = h - 1 ; j >= h - num ; j--) arr[j]++;
	}
	}
	start = 0; end = h - 1;
	sort(arr, arr + h);
	int min_num = *min_element(arr, arr + h);
	auto upper = upper_bound(arr, arr + h, min_num);
	auto lower = lower_bound(arr, arr + h, min_num);
	cout << min_num << " " << upper - lower;
	return 0;
	}

view raw 3020_2.cpp hosted with ❤ by GitHub

---

2022-01-03

Gold 5

- 이분 탐색

- 누적 합