백준 11722 - 가장 긴 감소하는 부분 수열 [파이썬]

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

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

---

풀이 과정

https://greentea31.tistory.com/34

백준 11053 - 가장 긴 증가하는 부분 수열 [파이썬]

가장 긴 증가하는 부분 수열 -> 가장 긴 감소하는 부분 수열임을 제외하면 위의 문제의 해결법과 풀이과정이 일치한다.

 

가장 긴 증가하는 부분 수열을 구하는 점화식

D[i] = max(D[J]) + 1 (j < i, A[j] < A[i])

 

에서 부등호만 다음과 같이 바꿔주고 코드로 구현하면 문제를 해결할 수 있다.

D[i] = max(D[J]) + 1 (j < i, A[j] > A[i])

 

 

---

소스 코드

import sys

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

d = [1 for _ in range(N)]

for i in range(N):
    for j in range(i):
        if A[j] > A[i]:
            d[i] = max(d[i], d[j] + 1)

print(max(d))