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

이분탐색과 점점 친해지는 중이다...
뭐해...? 라고 선톡 보낼 수 있는 정도...? 깔깔

요즘 시간을 재고 문제를 푸는 연습을 하고 있다.
이 문제의 핵심인 lower_bound, upper_bound를 파악하기까지는 13분이 걸렸지만, 그 후 47분 동안 삽질을 하여 총 1시간이 소요되었다...

문제링크

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

설명

개똥벌레가 파괴해야하는 장애물의 최솟값과 그러한 구간의 개수를 구해야하는 문제이다.

입력 순서에 따라 장애물이 석순, 종유석으로 다르기 때문에 따로 입력을 받아주고 정렬한 뒤, lower_bound, upper_bound를 활용하였다.

위 두 알고리즘의 시간복잡도는 log n이고, 모든 높이 구간에서 파괴해야하는 장애물의 개수를 구해야 하므로 총 시간복잡도는 h * log n이다.

기준 높이보다 작은 석순의 개수(s), 동굴의 높이에서 기준 높이를 뺀 길이를 초과하지 않는 종유석의 개수(e)를 구한 뒤, 이를 전체 개수에서 빼준 뒤 체크해두었다. 이를 그림으로 나타내면 다음과 같다.

예를 들어, 기준 높이가 4일 때, 4보다 작은 석순의 개수(s)는 2개고, 동굴의 높이에서 기준 높이를 뺀(7 - 4 = 3) 길이를 초과하지 않는 종유석의 개수(e)는 2개이므로, 전체 장애물의 개수(6)에서 s와 e를 빼준 2가 높이가 4일 때, 파괴해야하는 장애물의 개수가 된다.

이 부분에서 나도 계속 헷갈려서 20분 정도를 더 허비한 거 같다.

시간을 재면서 푸니까 더욱 조급해지는 거 같다. 조금 더 마음을 편하게 하고 풀어야겠다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> stalactite, stalagmite, ans(500001);

int n, h, num, s, e, m, mincnt = 200000;

void input()
{
	cin >> n >> h;
	for (int i = 0; i < n; i++)
	{
		cin >> num;
		if (i % 2)
			stalactite.push_back(num);
		else
			stalagmite.push_back(num);
	}
	sort(stalagmite.begin(), stalagmite.end());
	sort(stalactite.begin(), stalactite.end());
}

void solution()
{
	for (int i = 1; i <= h; i++)
	{
		s = upper_bound(stalactite.begin(), stalactite.end(), h - i) - stalactite.begin();
		e = lower_bound(stalagmite.begin(), stalagmite.end(), i) - stalagmite.begin();
		mincnt = min(mincnt, n - s - e);
		ans[n - s - e]++;
	}
	cout << mincnt << ' ' << ans[mincnt];
}

void solve()
{
	input();
	solution();
}

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

	solve();
	return 0;
}