[BOJ] 3020번 : 개똥벌레

문제 링크 : 백준 3020번

[문제 접근]

범위가 (2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000)인 것으로 보아 브루트 포스로는 시간 초과가 날 것 같아서 이분탐색으로 방향을 잡았다.
처음에는 문제의 높이를 기준으로 잡고 탐색했는데 거의 다 만들었을 때 문제를 잘못읽었다는 것을 알았다.
파괴해야하는 장애물의 최솟값을 기준으로 구해야 하는 문제였다.

따라서 lower_bound와 upper_bound를 이용해서 해당 높이일 때 파괴해야하는 개수를 구했다.

[소스 코드]

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

using namespace std;

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,h;
    cin >> n >> h;
    vector<int> a;
    vector<int> b;
    for(int i=0 ; i<n ; i++) {
        int l;
        cin >> l;
        if(i%2==0) a.push_back(l);
        else b.push_back(l);
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    int cnt=1;
    int ans = 300000;
    for(int i=1 ; i<=h ; i++) {
        int temp = a.size() - (lower_bound(a.begin(), a.end(), i) - a.begin());
        temp += b.size() - (upper_bound(b.begin(), b.end(), h-i) - b.begin());

        if(ans == temp) cnt++;
        else if(ans>temp) {
            cnt=1;
            ans = temp;
        }
    }
    cout << ans << " " << cnt;
}