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

컴퓨터는 1초에 1억번까지의 연산이 가능하다고 생각하면 된다.

이는 시간복잡도를 계산할 때 유용하게 사용하는 꿀팁이다.

이 문제의 경우 n이 1000개까지 입력되므로,

n 제곱까지의 시간복잡도는 허용된다고 생각하면 된다.

# n 입력
n = int(input())

# a 입력
a = list(map(int, input().split()))

# dp 설계
dp = [
    0 for _ in range(n)
]

# dp 초기설정
dp[0] = 1

# 점화식 활용, dp 채워넣기
for i in range(1, n):

    # 최댓값 설정
    M = 0

    # i-1 까지 탐색하면서
    for j in range(i):

        # a[i] 보다 크고, 현재 최댓값보다 dp값이 크다면,
        if a[j] > a[i] and dp[j] > M:
            
            # 최댓값 갱신
            M = dp[j]
    
    # dp값 갱신
    dp[i] = M + 1

# 출력
print(max(dp))