[백준] 3020. 개똥벌레

문제

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

풀이

해당 구간의 높이에 따라 부딪히는 석순과 종유석의 개수를 체크해주기만 하면 된다. 가령 첫번째 구간에선 높이가 1이상인 것들은 전부 파괴하므로 석순은 길이가 1이상, 종유석은 전체높이 - 1 이상인 것들을 전부 찾아준다. 이 때 브루트포스로 하면 너비 20만에 높이 50만 짜리는 무조건 시간초과가 나므로 이분탐색의 upper_bound & lower_bound를 이용하여 해결해준다.

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>

using namespace std;

// 이진 탐색으로 구현한 lower_bound
long long lower_bound(int arr[], int n, int key){
    int start = 0; int end = n;
    while(end - start > 0){
        int mid = (start + end) / 2;
        if(arr[mid] < key){
            start = mid + 1;
        }
        else if(arr[mid] >= key){
            end = mid;
        }
    }
    return end;
}
// 이진 탐색으로 구현한 upper_bound
long long upper_bound(int arr[], int n, int key){
    int start = 0; int end = n;
    while(end - start > 0){
        int mid = (start + end) / 2;
        if(arr[mid] <= key){
            start = mid + 1;
        }
        else if(arr[mid] > key){
            end = mid;
        }
    }
    return end;
}

int main(){

    int bot[100010], top[100010];
    int N, H; cin >> N >> H;
    int less_destroy = N, less_cnt = 1;
    for(int i = 0; i < N / 2; i++){
        cin >> bot[i] >> top[i];
    }

    sort(bot, bot + N / 2); sort(top, top + N / 2);

    // ex) 1번째 구간 -> 길이가 1 이상 -> 석순은 길이가 1 이상이며 종유석은 길이가 H - 1 이상인 것.
    for(int i = 1; i <= H; i++){
        // 석순에 대한 범위
        int low_bot_dest = lower_bound(bot, N / 2, i);
        int up_bot_dest = N / 2;
        // 종유석에 대한 범위
        int low_top_dest = lower_bound(top, N / 2, H - i + 1);
        int up_top_dest = N / 2;

        int bot_cnt = up_bot_dest - low_bot_dest;
        int top_cnt = up_top_dest - low_top_dest;

        // 이전에 찾은 최소 파괴 수가 현재 파괴한 수와 같으면 개수를 추가한다. 
        if(less_destroy == bot_cnt + top_cnt) less_cnt++;
        // 그렇지 않으면 상황에 따라 갱신하거나 그대로 둔다.
        else{
            if(less_destroy > bot_cnt + top_cnt){
                less_destroy = bot_cnt + top_cnt;
                less_cnt = 1;
            }
        }
    }

    cout << less_destroy << " " << less_cnt;
    return 0;
}