[백준-11053] 가장 긴 증가하는 부분 수열 / Python

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

11053번: 가장 긴 증가하는 부분 수열

n = int(input())
arr = list(map(int, input().split()))
d = [0] * n

for i in range(n):
    for j in range(i):
        if arr[i] > arr[j] and d[i] < d[j]:
            d[i] = d[j]
    d[i] += 1

print(max(d))

 

해설

처음 문제를 접했을 땐 이전 값들 중 현재 값보다 작은 인덱스를 기억해서 푸는 문제인줄 알았는데 아니었다😅

좀 더 간단하게 생각해보니 이전 값들 중 현재 값보다 작은 값이면서 현재 값까지의 길이보다 더 큰 길이를 만족하면 현재 값 길이는 해당 이전 값의 길이 + 1이 된다.