[백준] 11053 가장 긴 증가하는 부분 수열 python

www.acmicpc.net/problem/11053

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

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

for i in range(1, n + 1):
    max_val = 0
    for j in range(i):
        if arr[j] < arr[i] and max_val < dp[j]:
            max_val = dp[j]
    dp[i] = max_val + 1
print(max(dp))

점화식을 어떻게 세워야할지 고민을 많이 했다.

아무리 생각해도 점화식을 떠올릴수 없었고 구글링을 해서 찾아보았다.

여기에 사용된 방법은 이전 원소들을 확인하면서 해당 원소보다 큰 값인 경우에서 최대값을 찾고, 그 값에 1을 더하는 방식이다.

그리고 arr와 dp의 맨 앞에 0을 추가하여 원소 값이 최소인 경우 max_val가 0이 되는걸 피했다.

 

dp의 길은 너무나도 멀다