[COCI] 백준 3020 - 개똥벌레

icpc.me/3020

 

종유석과 석순을 살펴보면 어떤 식으로 나열되어 있든 부숴야 될 갯수에는 변함이 없다는 것이다.

 

그 즉슨 종유석과 석순을 정렬하고 이진 탐색을 통해 어떤 높이에서 몇개 부숴야 하는지 확인하면 빠르게 풀 수 있음을 알 수 있다.

 

1부터 h까지 반복문을 돌려 해당 높이에서 최소한으로 부술 수 있는지, 최소한으로 부술 수 있는 경우가 몇개인지 확인하면 AC를 받을 수 있다.

 

시간복잡도 $O(HlogN)$

 

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
 
int n, h;
int breaking = 1e9;
int cnt;
 
int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
 
    cin >> n >> h;
 
    vector<int> down(n / 2), up(n / 2);
 
    for (int i = 0; i < n / 2; ++i)
        cin >> down[i] >> up[i];
    
    sort(down.begin(), down.end());
    sort(up.begin(), up.end());
 
    for (int i = 1; i <= h; ++i)
    {
        int tmp = 0;
 
        tmp += down.size() - (lower_bound(down.begin(), down.end(), i) - down.begin());
        tmp += down.size() - (lower_bound(up.begin(), up.end(), h - i + 1) - up.begin());
 
        if (tmp <= breaking)
        {
            tmp == breaking ? ++cnt : cnt = 1;
            breaking = tmp;
        }
    }
 
    cout << breaking << ' ' << cnt;
}