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

import sys
input = sys.stdin.readline

def BOJ11722() :
  n = int(input())
  l = list(map(int, input().split()))
  dp = [1 for _ in range(n)]
  
  for i in range(n) :
    for j in range(i) :
      if l[i] < l[j] :
        dp[i] = max(dp[i], dp[j] + 1)

  print(max(dp))

BOJ11722()

 

접근 방법 :

1. 가장 긴 증가하는 부분 수열의 번외편이다. 
이전의 최대 길이를 이용해야 하므로 dp를 이용해 주었다.

 

2. 현재 비굣값에서 이전 인덱스까지의 값을 모두 탐색해 주면서 자신보다 큰 값이 있으면 그 값에서의 길이 + 1과 현재 최대 길이를 비교해 준다.

 

 

 

 

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

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