[백준 1912 실버2] 가장 긴 증가하는 부분 수열 (DP/파이썬) 읽기복습필

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

n = int(input())
arr = list(map(int, input().split()))
dp = [0 for _ in range(n)]

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

print(max(dp))

Tech:

딱히 테크닉이랄건 별로 없지만, dp이전에 자기보다 작은 수 중 가장 많이 증가하는 수열을 자기 수열로 가져오는 기술을 썼다.

그냥 로직만 읽어봐도 충분할듯