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

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

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

 

<풀이>

 

2022.03.06 - [# Coding/# 백준] - [백준 / 11053] 가장 긴 증가하는 부분 수열 - Python

[백준 / 11053] 가장 긴 증가하는 부분 수열 - Python

이 문제와 매우 비슷하다.

 

현재 수가 이전의 수들과 비교하면서, 만약 더 작다면 이전의 수까지의 부분 수열 길이 +1이거나 현재의 부분 수열 값중 더 큰값을 유지하면 된다.

 

for i in range(N):
    for j in range(i):
        if arr[i] < arr[j]:
            dp[i] = max(dp[i], dp[j]+1)

 

 

 

<전체 코드>

 

N = int(input())

arr = list(map(int, input().split()))
dp = [1 for _ in range(N)]

for i in range(N):
    for j in range(i):
        if arr[i] < arr[j]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))