백준 3015번 오아시스 재결합 (boj/3015.c)

조금 새로운 이진탐색 문제입니다.

직관적으로는 스택을 사용해서 풀 수 있지만 그렇게 풀면 시간복잡도가 N^2이 되버리므로 나락을 가버립니다.

스택에 들어가는 값이 항상 정렬되있다는 사실을 활용, 이진탐색으로 시간복잡도를 NlogN까지 올릴 수 있습니다.

#include <stdio.h>

int stk[500000] = { 0, };
int srcs(int val, int sze){
    int lft=0, rht=sze-1, mid;
    for(mid=(lft+rht)/2;lft<=rht; mid=(lft+rht)/2){
        if((!mid && stk[mid]<val) || (stk[mid]<val && stk[mid-1]>=val)){ return mid; }
        else if(stk[mid]>= val){ lft=mid+1; }
        else{ rht=mid-1; }
    }
    return sze;
}
int srce(int val, int sze){
    int lft=0, rht=sze-1, mid;
    for(mid=(lft+rht)/2;lft<=rht;mid=(lft+rht)/2){
        if((!mid && stk[mid]<=val) || (stk[mid]<=val && stk[mid-1]>val)){ return mid; }
        else if(stk[mid]>val){ lft=mid+1; }
        else{ rht=mid-1; }
    }
    return mid;
}
int main(void){
    int N, inp;
    int sze = 0;
    int s, e;
    long long cnt = 0;
    scanf("%d %d", &N, &inp);
    stk[sze++] = inp;
    for(int i=1;i<N;i++){
        scanf("%d", &inp);
        if(inp < stk[sze-1]){ 
            cnt++; stk[sze++]=inp;
            continue; }
        s = srcs(inp, sze);
        e = srce(inp, sze);
        cnt += e?sze-e+1:sze;
        stk[s] = inp; sze=s+1;
    }
    printf("%lld\n", cnt);
    return 0;
}