[Python] 백준 11055 가장 큰 증가 부분 수열

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

11055번: 가장 큰 증가 부분 수열

 

코드 작성

dp = [0] * 1001
n = int(input())
arr = list(map(int, input().split()))
dp[0] = arr[0]
for i in range(n):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j] + arr[i])
        else:
            dp[i] = max(dp[i], arr[i])
print(max(dp))

코드  풀이

#1 문제이해

가장 큰/긴 증가하는 부분수열의 비슷한 형태이다.

점화식 dp[i] = max(dp[i], dp[j] + arr[i])를 기억.

 

풀고보면 쉬운문제인데 완전히 이해하기까지 왜 그리 시간이 걸리는지...

하나의 문제를 완전히 이해하는데 8일이란 시간이 걸리면 양호한 편인듯...