[Python] 백준 11722번: 가장 긴 감소하는 부분 수열 풀이

 

소스코드

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

 

가장 긴 증가하는 수열과 같은 논리의 문제라서 쉽게 풀었다.

dp는 1로 초기화해놓고, 이중 for문을 이용해 i번째(현재 위치) 수와 0부터 i-1까지의 수(j) 를 비교하면서

만약 앞에 있는 수가 i보다 더 클 때, 그 때의 dp값은 j의 dp보다 1 큰 값이 될 수 있다.