[백준] 3020 개똥벌레

백준 3020 개똥벌레

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

• 문제의 태그에 이분 탐색이 있어서 개똥벌레가 날아가는 구간의 높이 h를 이분 탐색하는 풀이를 사용해야 하는 문제로 예상하였고, 그렇게 문제에 접근하려 하니 알고리즘의 정당성을 생각해내기 어려웠다

• 나중에 풀이를 알게 되니, 만나게 되는 석순의 개수와 종유석의 개수를 계산하기 위해 lower_bound 함수를 사용하기 때문에 이분 탐색 태그가 달린 문제였다

• 문제의 태그에 의존하여 접근하지 말고, 혼자 힘으로 풀어보자

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

int N, H;
     
vector<int> bottom; //석순
vector<int> top;    //종유석

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

	cin >> N >> H;

	for (int i = 0; i < N; ++i) {
		int input;
		cin >> input;

		if (i % 2 == 0) bottom.push_back(input);
		else top.push_back(input);
	}

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

	int minObstacle = N;
	int cnt = 0;

	//개똥벌레가 날아가는 구간의 높이 h
	for (double h = 0.5; h < H; ++h) {
		int obstacle = 0;
		
		//만나게 되는 석순의 개수
		obstacle += bottom.size() - (lower_bound(bottom.begin(), bottom.end(), h) - bottom.begin());
		
		//만나게되는 종유석의 개수
		obstacle += top.size() - (lower_bound(top.begin(), top.end(), H - h) - top.begin());

		if (minObstacle > obstacle) {
			minObstacle = obstacle;
			cnt = 1;
		}
		else if (minObstacle == obstacle) {
			++cnt;
		}
	}

	cout << minObstacle << " " << cnt;
	return 0;
}

📌참고자료

• 백준 3020 개똥벌레 풀이
  https://woongsios.tistory.com/255