12014 - 주식

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

국정원 소프트웨어 SW 공채 역량평가 샘플 예제
(여기 참조)

주어진 배열의 LIS의 길이가 $K$ 이상이면 1, 아니면 0을 출력하면 된다.

$N$의 범위로 보아 시간복잡도가 적당한 LIS를 사용한다. 길이만 알면 되서 $O(NlogN)$으로 작성했다.

#include <bits/stdc++.h>
using namespace std;

int LIS(vector<int>& a){
    vector<int> v(1, a.front());
    for(int i=1; i<a.size(); ++i){
        if(v.back() < a[i]){
            v.push_back(a[i]);
        }
        else if(v.back() > a[i]){
            *lower_bound(v.begin(), v.end(), a[i]) = a[i];
        }
    }
    return v.size();
}

int main(){
    int tc, T;
    scanf("%d", &T);
    for(tc=1; tc<=T; ++tc){
        int n, k;
        scanf("%d %d", &n, &k);
        vector<int> a(n);
        for(int i=0; i<n; ++i) scanf("%d", &a[i]);
        printf("Case #%d\n%d\n", tc, LIS(a) >= k);
    }
    return 0;
}