가장 긴 증가하는 부분 수열 4 풀이

문제 링크: https://www.acmicpc.net/problem/14002

백준 알고리즘 기초 1/2 400에서 11번째 - 14002번 가장 긴 증가하는 부분 수열 4를 풀어보았다.

 

풀이: 가장 긴 증가하는 부분 수열의 길이와 그 수열을 출력하는 문제이다.

파이썬의 경우, 수열을 출력하는 부분을 수열의 길이와 같이 하고자 했으나, 다른 사람들의 풀이를 참고해 분리했다.

 

C++

 

Python

n=int(input())
arr=list(map(int,input().split()))
dp=[1 for i in range(1001)]
for i in range(1,n):
	for j in range(0,i):
		if arr[j]<arr[i]:
			dp[i]=max(dp[i],dp[j]+1)
m=max(dp)
print(m)
res=[]
for i in range(n-1,-1,-1):
	if dp[i]==m:
		res.append(arr[i])
		m-=1
print(*reversed(res))

Java