[Python]동적계획법과 최단거리 역추적 백준 14002,14003

 문제

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

 문제

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

수열 시리즈 4번째이다.

2번째는 이분 탐색을 이용하여야 한다.  이전에 풀지 못하여 가장 긴 증가하는부분수열

 2를 해결하고 이문제로 넘어왔다.이번에는 길이를 구하는 문제가 아닌 증가하는 수열을

 구하는 문제이다.

14002와 14003의 풀이를 같이 하였다.

먼저 이전처럼 이분 탐색을 이용하였으며 각 인덱스의 가장 긴 증가하는 부분수열의 길이

뿐만 아니라 현재 인덱스와 이전

인덱스도 저장하여 구현하였다.

import sys
 
N=int(sys.stdin.readline())
A=list(map(int,sys.stdin.readline().split()))
DP=[[-1000000001,-1]]#현재 인덱스 저장
Trace=[0]*N#이전 인덱스가 어디인지 저장
 
 
#2분법을 통해 순서찾기
for i in range(N):
 
    low=0
    high=len(DP)-1
 
    while low<=high:#A[i]보다 작거나 같은수중에 제일 큰거 위치 찾기
        mid=(low+high)//2
        if DP[mid][0]<A[i]:
            low=mid+1
        else:
            high=mid-1
 
    if low>=len(DP):#위치가 배열보다 크다면 넣어준다
        Trace[i]=DP[low-1][1]
        DP.append([A[i],i])
    else:#해당 위치의 숫자를 바꿔준다.항상 작거나 같은수를 반환하기때문에 비교하지 않아도된다.
        DP[low][0]=A[i]
        #현재 인덱스 위치와 이전 인덱스 위치도 같이 저장해준다.
        DP[low][1]=i#현재 인덱스저장
        Trace[i]=DP[low-1][1]#이전 인덱스위치
# print(DP)
# print(Trace)
print(len(DP)-1)# 가장 긴수열 길이
 
result=[]
cur_index=DP[len(DP)-1][1]#처음 인자 넣기
# result.append(DP[len(DP)-1][0])
while cur_index!=-1:#추적하여 넣기
    result.append(A[cur_index])
    cur_index=Trace[cur_index]
 
for i in range(len(result)-1,-1,-1):#반대로 출력
    print(result[i],end=" ")