[백준/Python] 11722 가장 긴 감소하는 부분 수열

https://www.acmicpc.net/problem/11722

11722번: 가장 긴 감소하는 부분 수열

11053번(https://www.acmicpc.net/problem/11053)

가장 긴 증가하는 부분 수열의 문제에서 반대로 생각하면 된다. 

 

증가하는 부분수열 문제에서는

현재 인덱스 값(array[i])이 앞의 인덱스(array[j])의 값보다 클 때(array[i] > arary[j]) DP값을 증가시켰다면,

 

감소하는 부분 수열 문제에서는

현재 인덱스 값 보다 앞의 인덱스 값이 클 때(array[i] < array[j]) DP값을 증가시켰다. 

 

n = int(input())

dp = [1] * n
array = list(map(int, input().split()))

for i in range(n):
    for j in range(i):
        if array[i]<array[j] and dp[i]<=dp[j]:
            dp[i] += 1


print(max(dp))

 

 

증가 부분 수열 문제를 풀었기에 쉽게 해결하긴 했지만,

여전히 완벽하게 숙지되지 않아 계획한 로드맵을 다 풀고 나서 다시 복습해야겠다고 생각했다.