2019-12-22

알고리즘 문제풀이 2019-12-22

boj 2869 - 달팽이는 올라가고 싶다

종료조건, 반복문 조건 및 나가서 0처리가 신경쓸 부분. 이분 탐색에 익숙해져야 쉬워질 거 같다. 10억까지인 수들의 곱셈이 있어서 혹시 몰라 ll로 함.

cpp solution

// https://www.acmicpc.net/problem/2869
// 달팽이는 올라가고 싶다
// 

void solve(){
    ll A,B,V;
    cin>>A>>B>>V;
    ll diff=A-B;
    
    ll left=0;
    ll right=1000000001;
    ll mid=right/2;

    while(left<right){
        if(mid*diff+B<V){
            left=mid+1;
        } else {
            right=mid;
        }
        mid=(left+right)/2;
        // cout<< left << ' ' << right << ' ' << mid << endl;

    }
    if(mid==0) mid++;
    if(mid*diff+B<V){
        mid++;
    }

    cout<<mid;
    
}

boj 1920 - 수 찾기

before 주어진 배열에 각 수들이 존재하는지 확인. 정렬한 후 이분탐색

after cout에 endl써서 한 번 시간초과남.

cpp solution

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

void solve(){
    int N;cin>>N;
    int t;
    vi arr;
    rep(N, t){
        int tmp;
        cin>>tmp;
        arr.push_back(tmp);
    }

    std::sort(all(arr));
    // rep(N,t){
    //     cout<<arr[t] << ' ';
    // }
    // cout <<endl;

    int M;cin>>M;
    rep(M, t){
        int T;cin>>T;
        int left=0,right=N-1;
        int mid=(left+right)/2;
        while(left<right){
            if(arr[mid]>=T){
                right=mid;
            } else {
                left=mid+1;
            }
            mid=(left+right)/2;
        }        
        int ans=0;
        if(arr[mid]==T) ans=1;
        cout<<ans<<'\n';
    }
    
}