DP/최단거리 역추적. [14003]

[1. 문제 설명]

수열의 길이가 최대 1백만이 주어 질 때,

이 수열의 최장 부분 수열의 길이와

최장 부분 수열을 출력한다.

 

수열의 각 원소는 x 는 아래와 같은 범위를 갖는다.

[-10억, 10억]

---

[2. 풀이 접근]

수열의 길이가 최대 1백만 이므로, N² 알고리즘으로는 LIS 의 길이조차 찾을 수 없다.

LIS 의 길이는 nlogn 으로 찾을 수 있다.

=> 다음 풀이를 참조...

 

문제는 LIS 를 출력하는 것이다.

LIS 의 길이를 찾기 위해 사용 한 배열이 항상 LIS 가 됨을 보장하지 않는다.

 

아래와 같은 입력을 생각하면, 

A = {1, 10, 100, 9}

LIS 는 {1, 10, 100} 인데,

길이를 찾기 위해 사용 한 배열을 그대로 출력하면

{1, 9, 100} 이 출력된다.

 

정확한 LIS 를 출력하기 위해 한가지 생각 해 볼만한 것은

LIS 길이를 찾기 위해 사용 한 배열 내 마지막 원소는

LIS 의 마지막 원소라는 것이 보장된다는 것이다.

=> 값도 제일 크고, 원래 수열의 위치(index) 역시 제일 크다.

 

그래서, bottom-up 방식으로 LIS 의 마지막 원소부터 첫번째 원소까지 역탐색을 하여 출력하는 것이다.

아래 코드에서 solve() 수행 후, index 배열을 출력해서 살펴보면 어느 정도 감을 잡을 수 있다.

---

[3. 코드]