[백준] 3020. 개똥벌레

[문제]

www.acmicpc.net/problem/3020

 

[풀이]

 

처음에는 반복문을 사용해서 풀려고 했지만 N,H 범위를 생각해서 따지면

반복문 10억번에 1초라고 생각하면 20,000 * 50,000 이므로 1초를 훨씬 넘길 것이다. 

 

따라서 이분 탐색 방법으로 풀어야겠다고 생각했다.

 

 lower_bound는 x 이상인 값이 처음 나오는 index를 return하고

upper_bound는 x 이하인 값이 처음 나오는 index를 return 하므로 

 

전체 갯수에서 return 된 값을 빼면 파괴하는 장애물의 수를 구할 수 있다.

 

[코드]

 

시간 : 60ms

( 이분 탐색 직접 구현해서 다시  풀어봐야겠다.)

 

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

#define MAX 100000

using namespace std;

int N,H;

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int res = 1e9;
    cin >> N >> H;
    
    vector <int> up(N/2);
    vector <int> down(N/2);
    
    for(int i=0;i<N/2;i++)  cin >> down[i]>> up[i];

    int total=1;
       
    sort(down.begin(),down.end());
    sort(up.begin(),up.end());
    
    for(int i=1;i<=H;i++)
    {
        int cnt = down.size() - (lower_bound(down.begin(), down.end(),i)-down.begin());
        cnt += up.size() - (upper_bound(up.begin(), up.end(),H-i)-up.begin());
        
        
        if(res == cnt ) total++;
        else if(res > cnt ){
            res = cnt;
            total=1;
        }

    }

    cout << res << " " << total;
    return 0;
    
}