[백준] 3020 개똥벌레

lower_bound를 이용하여 풀 수 있는 문제다

x축에서의 좌표를 홀,짝으로 나눠 높이를 저장하고 

높이 y로 지나갈 때 각각의 좌표를 지나가는지 확인하면 된다

이 부분을 배열을 정렬하고 lower_bound를 이용한다면 쉽게 구할 수 있다

홀수 일때는 찾을때 높이에서 빼서 거꾸로 찾으면 된다

 

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n,h;
int ans[200020];
vector<int> odd,even;
 
int main(){
    //freopen("input.txt","r",stdin);
    scanf(" %d %d",&n,&h);
    for(int i=0;i<n;i++){
        int x; scanf(" %d",&x); x--;
        if(i&1) odd.push_back(x);
        else even.push_back(x);
    }
    sort(odd.begin(),odd.end());
    sort(even.begin(),even.end());
    h--;
    int es = even.size();
    int os = odd.size();
    for(int i=0;i<=h;i++){
        int a = es-(lower_bound(even.begin(),even.end(),i)-even.begin());
        int b = os-(lower_bound(odd.begin(),odd.end(),h-i)-odd.begin());
        ans[a+b]++;
    }
    for(int i=0;i<=n;i++){
        if(ans[i]){
            printf("%d %d\n",i,ans[i]); return 0;
        }
    }
}