[12015] 가장 긴 증가하는 부분 수열 2

분류 : 이분 탐색
시간복잡도 : O(nlogn)

 

 

다이나믹 프로그래밍(DP) 문제이다. DP인 만큼 어떻게 이전 상태의 정보를 저장하고 사용할지가 핵심이다.

 

다음의 경우를 보자.

{1, 2, 3}, {5, 6, 7} 이 수열 A의 부분 수열이라고 할 때, 길이가 3으로 동일하다. 이 두 부분 수열의 다음으로 4가 주어졌을 때, 길이가 4가 되는 부분 수열은 {1, 2, 3} 이다.

이처럼 길이가 같을 때, 맨 마지막 숫자가 작을수록 효율적이다. (관찰)

 

그렇다면, 어떻게 마지막에 작은 숫자가 오도록 만들 수 있을까?

이진 탐색을 이용하면 된다.

 

이진 탐색을 이용한 최소값 갱신은 각 길이 (i + 1)에 대한 마지막 값이다. 즉, 경로가 아니라는 뜻이다.

따라서, 갱신 시에 길이에 관련하여 다음 숫자, 이전 숫자에 영향을 주지 않는다.

그림으로 표현하면 다음과 같다.

 

i	0	1	2	3	4	5
arr	10	20	10	30	20	50
dp	10	20	30	50

i	0	1	2	3	4	5
arr	10	20	15	30	25	40
dp	10	15	25	40