[백준] 11722: 가장 긴 감소하는 부분 순열

DP

가장 긴 감소하는 부분 순열

수열의 길이가 1000까지이기 때문에 O(n^2)의 알고리즘을 사용해서 문제를 풀 수있습니다.

가장 긴 증가하는 부분 수열문제에서 j가 i 보다 클때만 갱신 시켜주는 걸로 바꾸면 됩니다.

import sys
n = int(input())
lst = list(map(int, input().split()))
dp = [1] * (n)
for i in range(n):
	for j in range(i):
		if lst[i] < lst[j]:
			dp[i] = max(dp[i], dp[j]+1)
print(max(dp))