백준 11722 : 가장 긴 감소하는 부분 수열 (Python)

본문 링크

N=int(input())

a=list(map(int,input().split()))

dp=[0]*N

for i in range(N):
    for j in range(i):
        if a[i]<a[j] and dp[i]<dp[j]:
            dp[i]=dp[j]
    dp[i]+=1
print( max(dp) )

📌 어떻게 접근할 것인가?

가장 긴 증가하는 부분 수열 문제 와 아주 비슷한 문제이다.

가장 긴 증가하는 부분 수열 알고리즘에서 if 문을 조금 바꿔주면 해결된다.

if a[i]<a[j] and dp[i]<dp[j] 가 가지는 의미는 부분수열이 감소하면서 이전의 감소한 횟수보다 큰가? 라는 의미이다.

예제 입출력을 보자.

• 입력
  6
  10 30 10 20 20 10
• 출력
  2

실제 $DP$ 테이블의 변화는 다음과 같다.

10 에서 30 으로 값이 증가할때는 이전 인덱스 값을 그대로 가져온다.
만약 30 에서 10 으로 감소했다면 이전 인덱스 값에 +1 을 한 값을 가져온다.

10 에서 또다시 20 으로 증가했으므로 이전 인덱스 값을 그대로 가져온다.

이렇게 반복하면서 30 - 20 - 10 으로 최장 감소 연속 부분수열의 길이는 3이된다.

이중반복문을 통해 탐색하였기 때문에 시간복잡도는 $O(N^2)$ 이다.