[DP] 백준 11722번 “가장 긴 감소하는 부분 수열” Python 풀이

문제 링크

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

코드

import sys

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

# 아이템 역순 정렬
item_reversed = item[::-1]

# DP 테이블 생성
dp = [1] * n

for i in range(n):
    for j in range(i+1,n):
        # 현재 위치의 값(item_reversed[i])보다 비교 대상(item_reversed[j])보다 크면,
        # 증가하는 순서가 성립하므로 DP 테이블 업데이트
       if (item_reversed[i] < item_reversed[j]):
           dp[j] = max(dp[i]+1, dp[j])

print(max(dp))