[백준] 14003번 : 가장 긴 증가하는 부분 수열 5

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

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

해당 문제는 ans 테이블을 역추적하여 문제를 해결 할 수 있다.

단일 for문에서 ans테이블을 해당 원소를 삽입하였을때 자기자신의 위치를 기록한다. 자기자신의 위치를 기록해두어 dp테이블을 역 순회 하여 해당 길이가 증가되었을때의 원소를 찾는다.

 

1. arr[i]가 현재 배열의 마지막 원소보다 클 경우 - arr[i]는 현재 lis의 길이를 저장

2. arr[i]가 현재 배열의 마지막 원소보다 작을 경우 - bisect로 idx를 구한뒤 idx+1이 그 해당원소의 길이의 위치임으로 idx+1 값으로 저장

 

ans를 역추적하여 원소의 길이가 증가되었을때의 경우를 찾는다.

import bisect
n = int(input())
arr = list(map(int, sys.stdin.readline().split()))

ans=[0]*n
lis = [-1000000001]
for i in range(n):
    if arr[i]> lis[-1]:
        lis.append(arr[i])
        ans[i]=len(lis) # 추적하기 위한 값 업데이트
    else:
        temp = bisect.bisect_left(lis, arr[i])
        lis[temp] = arr[i]
        ans[i] = temp + 1 # 추적하기위한 값 업데이트

temp = [0] * len(lis)
cnt = len(lis)
for i in range(len(arr) - 1, -1, -1):
    if ans[i] == cnt:
        cnt-=1
        temp[cnt] = arr[i]

print(ans)
l = len(lis)
print(l-1)
print(*temp[1:])