백준 14003 가장 긴 증가하는 부분 수열 5

 

이분탐색으로 LIS를 찾을 때 사용하는 방법은
LIS 길이는 찾을 수 있지만 정확한 해당 수열은 아니다.
정확한 수열을 찾기 위해서 아래처럼 추가적인 작업이 필요하다.

a: 입력된 배열
l: LIS 배열
x: 입력데이터의 각 원소가 위 LIS 배열에 들어갈 때 인덱스를 저장해 두는 배열
    x[i] = 0 : 입력데이터에서 i번째 있는 숫자는 LIS배열 맨 앞에 있다.
m: x에서 찾은 최대값.
r: 해당 x에서 m을 가지고 있는 위치부터 역순으로 m을 하나씩 줄여가며 가장 먼저 만나는 x의 인덱스를 배열로 구성
r의 역순으로 정렬 후 각각의 r의 각 요소를 index로 하는 a값을 출력.

 

입력배열을 2 4 1 3 6 7 5 10 8 9 라고 할 때

l과 x는 아래와 같이 변화한다.

 

2 처리시: l [2]
2 처리시: x [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 

4 처리시: l [2, 4]
4 처리시: x [0, 1, 0, 0, 0, 0, 0, 0, 0, 0]

 

1 처리시: l [1, 4]
1 처리시: x [0, 1, 0, 0, 0, 0, 0, 0, 0, 0]

 

3 처리시: l [1, 3]
3 처리시: x [0, 1, 0, 1, 0, 0, 0, 0, 0, 0]

 

6 처리시: l [1, 3, 6]
6 처리시: x [0, 1, 0, 1, 2, 0, 0, 0, 0, 0]

 

7 처리시: l [1, 3, 6, 7]
7 처리시: x [0, 1, 0, 1, 2, 3, 0, 0, 0, 0]

 

5 처리시: l [1, 3, 5, 7]
5 처리시: x [0, 1, 0, 1, 2, 3, 2, 0, 0, 0]

 

10 처리시: l [1, 3, 5, 7, 10]
10 처리시: x [0, 1, 0, 1, 2, 3, 2, 4, 0, 0]

 

8 처리시: l [1, 3, 5, 7, 8]
8 처리시: x [0, 1, 0, 1, 2, 3, 2, 4, 4, 0]

 

9 처리시: l [1, 3, 5, 7, 8, 9]
9 처리시: x [0, 1, 0, 1, 2, 3, 2, 4, 4, 5]

 

 

 

from bisect import*

n,*a=map(int,open(0).read().split())
l=[]  # LIS를 저장할 리스트
x=[0]*n # 입력된 숫자를 LIS 리스트에 넣을 때 교체 혹은 추가되는 index 리스트

# 이진탐색을 수행하고 LIS 배열에 교체하거나 추가함. 그리고 해당 index를 기록
for e in a:p=bisect(l,e-1);l[p:p+1]=e,;x[i]=p

m=max(x) # 인덱스의 최대 값을 찾음
t=[]
for i in range(n-1,-1,-1): # index 리스트의 뒤에서 부터 탐색
 if x[i]==m:t+=i,;m-=1 # 인덱스 최대값부터 하나씩 줄여가며 index 리스트에서 가장 먼저 만나는 위치를 저장
print(len(l),*[a[i] for i in t[::-1]]) # 역순으로 출력

 

https://www.acmicpc.net/problem/14003