DP/최단거리 역추적. [14003]
[1. 문제 설명] 수열의 길이가 최대 1백만이 주어 질 때, 이 수열의 최장 부분 수열의 길이와 최장 부분 수열을 출력한다. 수열의 각 원소는 x 는 아래와 같은 범위를 갖는다. [-10억, 10억] [2. 풀이 접근] 수열의 길이가 최대 1백만 이므로, N2 알고리즘으로는 LIS 의 길이조차 찾을 수 없다. LIS 의 길이는 nlogn 으로 찾을 수 있다. => 다음 풀이를 참조... 문제는 LIS 를 출력하는 것이다. LIS 의 길이를 찾기 위해 사용 한 배열이 항상 LIS 가 됨을 보장하지 않는다. 아래와 같은 입력을 생각하면, A = {1, 10, 100, 9} LIS 는 {1, 10, 100} 인데, 길이를 찾기 위해 사용 한 배열을 그대로 출력하면 {1, 9, 100} 이 출력된다. 정확한 ..
