12014 - 주식

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

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

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

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

11568 - 민균이의 계략

최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 로 해결할 수 있다.

이 문제는 $O(N^2)$ 도 가능하다. 현재 자신보다 이전에 더 작은 수가 있다면, 현재값과 그 수까지의 LIS+1 중에 더 큰 값으로 선택하면 된다.

코드로 구현하면 아래와 같다.

int answer = 0;
for(i=0; i<n; ++i){
    for(j=i; j>=0; --j){
        if(a[j] < a[i]){
            LIS[i] = max(LIS[i], LIS[j]+1);
        }
    }
    answer = max(LIS[i], answer);
}
printf("%d", answer+1);

3745 - 오름세

최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 로 해결할 수 있다.
$N$이 적당히 크므로 $O(N^2)$ 은 안되고 $O(NlogN)$ 으로 해결해야 한다.