백준 14002 [가장 긴 증가하는 부분 수열 4] 파이썬

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

14002번: 가장 긴 증가하는 부분 수열 4

#백준 14002
import sys
n=int(sys.stdin.readline())
lst=list(map(int,sys.stdin.readline().split()))
dp=[0]*(n)
s=[[] for _ in range(n)]
for i in range(n):
    for j in range(i):
        if lst[i]>lst[j] and dp[i]<dp[j]:
             dp[i]=dp[j]
             s[i]=list(map(int,s[j]))
    dp[i]+=1
    s[i].append(lst[i])
print(max(dp))
for i in (s[dp.index(max(dp))]):
    print(i,end=' ')

#백준 14002 다른풀이
N=int(input())
arr=list(map(int,input().split()))
dp=[1]*N
for i in range(1,N):
    for j in range(i):
        if arr[i]>arr[j]:
            dp[i]=max(dp[i],dp[j]+1)
print(max(dp))
order=max(dp)
lst=[]
for i in range(N-1,-1,-1):
    if dp[i]==order:
        lst.append(arr[i])
        order-=1
lst.reverse()
for i in lst:
    print(i,end=' ')