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

 

n = int(input())
A = list(map(int,input().split()))
# A에 저장된 각 값들까지의 가장 긴 증가하는 부분 수열의 길이를 저장하는 배열
# A에 저장된 0번째 수까지의 가장 긴 증가부분수열의 길이는 1이므로
# 1로 초기화함
dp=[1]*n

# A에 저장된 1번째값부터 자신의 앞에 있는 수들과 비교를 함
for i in range(1,n):
    for j in range(i):
    	# 자신이 더 크다면 기존의 증가부분수열의 길이와
        # 부분수열에 자기자신을 추가했을 때의 길이 중 더 긴 것으로 업데이트함
        if A[i]>A[j]:
            dp[i] = max(dp[j]+1, dp[i])

# 가장 긴 증가부분수열의 길이를 저장함
order = max(dp)
# 증가부분수열의 실제 값을 저장할 리스트
subsequence = []

# dp테이블을 뒤에서부터 탐색함
for i in range(n-1,-1,-1):
	# dp[i]==order라는 건 A[i]가 부분수열의 값이라는 뜻
    if dp[i]==order:
        subsequence.append(A[i])
        order -= 1
        
# subsequence에는 증가부분수열이 역순으로 저장되어있으니 다시 뒤집어줌
subsequence.reverse()
# 가장 긴 증가부분수열의 길이
print(max(dp))
# 가장 긴 증가부분수열의 값
print(*subsequence)