[BOJ / Python] 11722 가장 긴 감소하는 부분 수열

😈 문제 설명

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

 

🔐 문제 풀이 

1️⃣ 부분 수열의 최소 길이는 1 이므로 dp 배열을 수열의 크기 만큼 1로 초기화한다. 

dp = [1] * n

 

2️⃣ 수열에 담긴 숫자를 하나씩 꺼내 앞에 있는 숫자들을 모두 탐색하게 한다. 그러다가 큰 수를 발견하게 된다면 부분 수열이 존재하는 것 이므로 dp 배열의 값을 업데이트한다. 

(앞에 있는 수의 수열 길이 + 1과 현재 dp 값을 비교한 뒤 큰 값으로 업데이트)

for i in range(1, n):
    for j in range(i):
        if data[j] > data[i]:
            dp[i] = max(dp[j] + 1, dp[i])

 

3️⃣ dp 배열에서 가장 큰 값이 가장 긴 감소하는 부분 수열의 길이가 된다. 

print(max(dp))

 

🪄 코드

# https://www.acmicpc.net/problem/11722
# 가장 긴 감소하는 부분 수열

import sys
input = sys.stdin.readline

n = int(input())
data = list(map(int, input().split()))
dp = [1] * n

for i in range(1, n):
    for j in range(i):
        if data[j] > data[i]:
            dp[i] = max(dp[j] + 1, dp[i])

print(max(dp))