Almost-K Increasing Subsequence
면접 대비시간 제한1초메모리 제한256 MB
주어진 수열의 부분수열 중에서 연속한 두 원소가 감소하는 위치가 K개 이하인 가장 긴 부분수열의 길이를 구한다.
문제
수열 a1, a2, ... , an이 주어진다. 이 수열에서 0개 이상의 수를 지워서 새로운 수열 b1, b2, ... , bm을 만들 수 있다. 이때 수열 b1, b2, ... , bm을 수열 a1, a2, ... , an의 Subsequence라고 부른다. 예를 들어, 수열 (1,2,4,5)의 Subsequence는 (1), (2, 5), (1, 2, 4, 5) 등이 있다.
수열 A = a1, a2, ... , an와 K가 주어질 때, 수열 A의 Longest Almost-K Increasing Subsequence의 길이를 구하고자 한다. Longest Almost-K Increasing Subsequence란 Almost-K Increasing Subsequence 중 가장 긴 수열을 말하며, Almost-K Increasing Subsequence는 다음과 같이 정의된다.
- 수열 B = b1, b2, ... , bm이 수열 A의 Subsequence라고 하자. 이때 모든 i = 1, 2, ... , m−1에 대하여 bi > bi+1인 i의 개수가 K개 이하이면, 수열 B를 수열 A의 Almost-K Increasing Subsequence라고 정의한다.
입력
첫 줄에 n, K(1 ≤ n ≤ 500, 0 ≤ K ≤ n)가 주어진다.
두 번째 줄에 정수 a1, a2, ... , an(1 ≤ ai ≤ 109)이 주어진다.
출력
수열 A의 Longest Almost-K Increasing Subsequence의 길이를 출력하라.
힌트
첫 번째 예제에서 Almost-0 Increasing Subsequence는 (1, 2, 3, 5), (1, 2, 3, 4)가 존재하며, 모두 길이가 4다.
두 번째 예제에서 Almost-1 Increasing Subsequence는 (1, 2, 3, 5, 4)로, 길이가 5다.