[Baekjoon/Python] 11053번: 가장 긴 증가하는 부분 수열 - 효과는 굉장했다!

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

 

알고리즘 분류

• 다이나믹 프로그래밍

 

 

SOLUTION

import sys

N = int(sys.stdin.readline())
N_list = list(map(int, sys.stdin.readline().split()))
dp = [1] * N # Dynamic Programming 이용

for i in range(N):
    for j in range(i):
        if N_list[i] > N_list[j]:
            # dp[현재 인덱스], dp[현재 이전의 인덱스]+1 값을 비교하여 더 큰 값으로 갱신
            dp[i] = max(dp[i], dp[j]+1) 

print(max(dp))