[DP] 백준 11722번: 가장 긴 감소하는 부분 수열(BOJ, Python, 파이썬)

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

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

문제

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.

 

✔ 풀이

이 문제는 11053번: 가장 긴 증가하는 부분 수열의 역이라고 생각하면 된다.

result[i]에 i까지 가장 긴 감소하는 부분 수열의 길이를 저장한다.

i이전에 오는 값을 j라고 하면s[j]>s[i]일 때 조건을 만족한다.

 

따라서 코드는 다음과 같다.

n=int(input())
s=list(map(int,input().split()))
result=[1]*n

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

print(max(result))