[알고리즘][백준] 11722번 가장 긴 감소하는 부분 수열 - 파이썬(python) 풀이

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

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

---

11053번 가장 긴 증가하는 부분 수열의 응용문제!

달라진 것은 증가 -> 감소 이 부분이라 if문에서

 

num[i] > num[j]인 것을 num[i] < num[j]로 변경해주기만 하면 된다.

import sys

n = int(sys.stdin.readline())

num = list(map(int, sys.stdin.readline().split()))

dp = [1] * n

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

print(max(dp))

11722_가장긴감소하는부분수열.py

0.00MB