링크
문제 요약
모든 원소가 unique 한 수열이 주어진다. 이때, UD 수열은 다음과 같이 정의된다. 주어진 수열의 연속 증가수열과 연속 감소수열의 길이가 모두 3 이상인 경우를 UD 수열이라 부른다. 가령 8 5 1 3 4 7 6 2 는, 8 5 1 / 1 3 4 7 / 7 6 2 이렇게 3개의 연속 증가/감소 수열이 있고, 모두 길이가 3 이상이므로 UD 수열이다. 주어진 수열의 sub-sequence 중 가장 긴 UD 수열의 길이를 찾는 문제이다.
관찰
문제에서 구하고자 하는 값이 특정 조건을 만족하는 가장 긴 sub-sequence 를 찾는 것이므로, DP를 이용하는 것이 적절해 보인다. 일단 값의 범위가 크기 때문에 DP 적용을 쉽게 하기위해 좌표 압축을 하도록 하자. 어차피 좌표 압축을 해도 기존의 원소가 모두 unique 하기 때문에 대소 관계는 서로 바뀌지 않는다. 이제 점화식 유도를 해보도록 하자.
어떤 수가 UD 부분 수열이 되기 위해서는 모든 연속 증가/감소 수열이 길이가 3이상이어야 하므로, 원소의 상태는 아래와 같이 4가지가 존재한다.
- 현재 원소($=x$)가 연속 증가수열의 마지막 원소이고 길이가 2이하.
- 현재 원소($=x$)가 연속 증가수열의 마지막 원소이고 길이가 3이상이거나 첫번째 연속 증가수열의 원소인 경우.
- 현재 원소($=x$)가 연속 감소수열의 마지막 원소이고 길이가 2이하.
- 현재 원소($=x$)가 연속 감소수열의 마지막 원소이고 길이가 3이상이거나 첫번째 연속 감소수열의 원소인 경우.
각각을 $D(x,0), D(x,1), D(x,2), D(x,3)$ 라고 편의상 표현하도록 하자. 유효한 UD 수열의 특징은 첫번째 연속 증가/감소수열의 길이만 3이상으로 설정하면, 그 이후에 증가/감소가 바뀌는 원소가 오면, 해당 연속수열의 길이는 최소 2가 됨이 보장된다는 것이다. 따라서 이를 고려해서 점화식을 작성하면 아래와 같다.
$D(x,0)=\max(0,D(y,3))+1 \ \ \ \ (y<x, 3\leq{D(y,3)})$
$D(x,1)=\max(D(y,0),D(y,1))+1 \ \ \ \ (y<x)$
$D(x,2)=\max(0,D(y,1))+1 \ \ \ \ (x<y, 3\leq{D(y,1)})$
$D(x,3)=\max(D(y,2),D(y,3))+1 \ \ \ \ (x<y)$
따라서 이 점화식을 풀면 된다. 답은 $\max(D(x,1),D(x,3)) \ \ (1\leq{x}\leq{N})$ 이고, 앞서 말한 유효한 UD 수열의 특징에 의해 해당 값이 3 이상이면 유효한 수열이다. (즉, 3보다 작은 값이면 답은 0이다.)
풀이
하지만 위의 풀이는 여전히 너무 느리다. 전체 상태의 개수가 $O(N)$, 각각의 상태를 해결하는데 $O(N)$ 이 걸리므로, Naive한 구현으로는 $O(N^2)$ 의 시간이 걸린다. 이를 최적화 하는 방법은 굉장히 간단한데, 우리가 참고해야할 범위가 연속적이라는 특징을 이용하면된다. 각 점화식마다 참고할 값의 범위는 현재 원소 $x$ 보다 큰 모든 수와, 작은 모든 수를 보게 된다. 따라서 DP 값을 최댓값 세그먼트 트리에 저장하여 관리하면, 상태 전이에 필요한 시간을 $O(\log{N})$ 으로 줄일 수 있으므로, 총 $O(N\log{N})$ 시간에 문제를 해결할 수 있다.