2633 : Lower Bound

dkswnkk 2022. 1. 14. 21:17

문제

Lower Bound

첫 줄에 한 정수 $n$과 찾고자 하는 값 $k$가 공백으로 구분되어 입력되고, 둘째 줄에 $n$개의 정수가 공백으로 구분되어 입력된다. (단, $2 <= n <= 100,000$ , 각 원소의 크기는 $100,000,000$을 넘지 않는다

codeup.kr

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    
    int n,k; cin>>n>>k;
    vector<int>v;
    
    for(int i=0; i<n; i++){
        int inp; cin>>inp;
        v.push_back(inp);
    }
    sort(v.begin(),v.end());
    
    int start=0, end = n-1;
    while(start<=end){
        int mid = (start+end)/2;
        if(v[mid]<k) start=mid+1;
        else end=mid-1;;
    }
    
    cout<<start+1;
}

풀이

단순 이분 탐색 구현 문제였습니다.

upper_bound, lower_bound STL이 있는 것은 알고 있지만, 해당 STL사용이 익숙하지 않아서 직접 구현했습니다.

채점

저작자표시 (새창열림)