백준 2550 전구

 

LIS 문제로 LIS 대상이 스위치별 전구리스트에서의 index

 

스위치 리스트 [2,4,1,5,3]
전구 리스트     [4,5,1,3,2]
스위치별 전구 index 리스트 [4,0,2,1,3] ==> LIS 대상.

 

from bisect import*
n,*l=map(int,open(0).read().split())
L=l[n:] # 전구(Light) 리스트
a=[L.index(e)for e in l[:n]] # 스위치별 전구 index 리스트
l=[] # LIS 저장용 배열
x=[] # a 원소처리시 l에서의 위치 저장용
for e in a:p=bisect(l,e-1);l[p:p+1]=e,;x+=p, # 이분탐색 및 l, x 갱신
m=max(x) # 최대위치값
t=[]
for i in range(n-1,-1,-1): # 역순으로
 if x[i]==m:t+=i,;m-=1 # 최대위치값부터 각각의 위치 구함.
print(len(l),*sorted(L[a[i]]for i in t))

 

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