[14003번] 가장 긴 증가하는 부분 수열5 (LIS, 이분탐색)

14003번: 가장 긴 증가하는 부분 수열 5

 

분석

D[i] : 0~i까지 i를 포함하는 가장 길게 가하는 수열의 길이

A[i]를 i번째 수열의 값이라고 정의하면 D[k]는 A[i]>A[K]를 만족하는 최대 수열의 길이

즉, A[i]보다 작은 값을 지니고 있는 수열의 최장 증가 수열의 길이들 중 최댓값을 찾아 해당 값에 +1 한 값을 D[i]에 저장

D[i] = max({D[k]}) +1 (k=1~i-1)

 

1. D 리스트를 맨 뒤에서부터 탐색해 최댓값과 동일 값을 가지는 최초 index의 A[]값을 출력
2. 그리고 값을 1만큼 감소시키고 index가 1이 될 때 까지 반복

 

풀이

import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
a.insert(0,0)

index=0
# 최장증가부분수열 길이
maxLength=1

# 현재 가장 유리한 증가수열 저장 리스트
b=[0]*1000001
b[maxLength]=a[1]
# 0~i까지 i를 포함하는 최장증가수열 길이 저장 리스트
d=[0]*1000001
d[1]=1
# 정답 수열 저장 리스트
res=[0]*1000001

def binarySearch(l,r,now):
    while l<r:
        mid=(l+r)//2
        if b[mid]<now:
            l=mid+1
        else:
            r=mid
    return l

for i in range(2, n+1):
    if b[maxLength]<a[i]: # 가장 마지막 수열보다 현재 수열이 큰경우
        # b리스트 끝에 a[i] 추가
        maxLength+=1
        b[maxLength]=a[i]
        d[i]=maxLength

    else:
        # 바이너리 서치를 이용홰 현재 수열이 들어갈 index 찾기
        index=binarySearch(1,maxLength, a[i])
        b[index]=a[i] # 현재 수열값 저장
        d[i]=index


print(maxLength)

index=maxLength
x=b[maxLength]+1

for i in range(n,0,-1): # 뒤에서부터 담색하면서 정답 수열 저장
    if d[i] == index and a[i] < x:
        res[index]=a[i]
        x = a[i]
        index-=1

for i in range(1, maxLength+1):
        print(res[i], end=' ')