boj 4198 : Trainsorting

Problem Solving

1ssrek 2016. 8. 16. 18:42

증가 부분수열, 감소 부분수열 을 이용하여 해결한다.

(n번째부터 시작하는 증가부분수열의 갯수) + (n번째부터 시작하는 감소부분수열의 갯수) - 1 의 최대값이 정렬된 train car의 최대 갯수.

시간복잡도는 n^2으로 하여 간단하게 풀었지만 nlogn으로 해결하는 방법도 가능하다.