문제 풀이

이분탐색을 통해 각 높이에 몇개의 석순, 종유석이 파괴될지 구한다.
석순, 종유석 따로 입력을받아 이분탐색을 위해 정렬을 하고, 1부터 최대 높이 h까지 이분탐색을 통해 몇개가 파괴될지 각각 구해주면 된다.

석순이 몇개 부숴질지 구하는 이분탐색에서는 r+1에 부숴지는 석순 중 가장 짧은 석순의 인덱스가 담길 것이고, 석순의 총 개수 - 가장 짧은 석순의 인덱스 = 파괴될 석순의 개수라고 볼 수 있다.

종유석도 비슷한 개념으로 접근하면 된다.

문제 링크

boj/3020

소스코드

PS/3020.cpp

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<stack>
#include<map>
#include<memory.h>
#include<queue>
using namespace std;

int bot[500001];
int top[500001];
vector<int> even;
vector<int> odd;

int n, h;

int main()
{

	cin >> n >> h;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		if (i % 2 == 0)
			even.push_back(a);
		else
			odd.push_back(a);
	}
	sort(even.begin(), even.end());
	sort(odd.begin(), odd.end());

	for (int i = 1; i <= h; i++)
	{
		int l = 0, r = even.size() - 1;
		while (l <= r)
		{
			int mid = (l + r) / 2;


			if (even[mid] < i)
			{
				l = mid + 1;
			}
			else
			{
				r = mid - 1;
			}

		}
		bot[i] = even.size() - (r + 1);

		l = 0, r = odd.size() - 1;
		while (l <= r)
		{
			int mid = (l + r) / 2;
			if (h - odd[mid] >= i)
			{
				l = mid + 1;
			}
			else
				r = mid - 1;
		}
		top[i] = odd.size() - l;

	}
	int m = 987654321;
	int c = 0;
	for (int i = 1; i <= h; i++)
	{
		int sum = top[i] + bot[i];
		if (sum < m)
		{
			m = sum;
			c = 1;
		}
		else if (sum == m)
		{
			c++;
		}
	}
	cout << m << ' ' << c;
}