[백준] 가장 긴 증가하는 부분 수열 4

출처:: www.acmicpc.net/problem/14002

분류:: dp

 

1. 문제 이해 및 해결과정

- dp[i]=arr[i]까지 수 중 가장 긴 증가하는 부분수열  A = {10, 20, 10, 30, 20, 50} 1) 10까지, 1개 2) 20까지, max( dp[i-1] + if 10>20 +1 , 1) 3) 10까지 , max( dp[i-1] -> 2개, 1(자기자신)) 4) 30까지, max( dp[i-1] + dp의 최대값보다 크다면

 

2. 풀이방법

  1. [python] dp

#가장 긴 증가하는 부분 수열 4
#https://www.acmicpc.net/problem/14002
import sys
sys.stdin = open("input.txt","r")
input=sys.stdin.readline
n=int(input())
arr=list(map(int,input().split()))
dp=[1]*(n+1) #최소 자기자신 길이임 

for i in range(1,n): #맨 뒤를 기준으로
    for j in range(i): #그 앞 항까지
        if arr[i]>arr[j]: #기준보다 작은게 있으면 
            dp[i]=max(dp[i],dp[j]+1)
maxlen=max(dp)
print(maxlen)
lis=[]
for i in range(n-1,-1,-1):
    if dp[i]==maxlen: #최대길이인 것 구하기
        lis.append(arr[i])
        maxlen-=1
print(' '.join(map(str,reversed(lis)))) #lis뒤집음

 

3. 오답원인

 

4. 알게된 점

정수형 리스트를 뒤집어서 join으로 출력하기

print(' '.join(map(str,reversed(lis)))) #lis뒤집음