[파이썬] 백준 11053 가장 긴 증가하는 부분 수열

< 처음 풀이 >

접근법을 아예 몰랐다.

 

< 해결 방법 > 

동적 풀이를 최대한 이용하려고 했다. 하지만 일정 단계에서 더 생각이 안나서 구글링을 통해 해결을 했다. dp 리스트를 만드는 과정까지는 생각을 해냈지만 이중 for 문을 통해 해결하는 방법은 못 떠올려서 구글링을 통해 풀었다.

 

 

import sys
 
a = int(input())
 
k = list(map(int,sys.stdin.readline().rstrip().split(" ")))
 
dp = [0]*a
 
 
 
 
for i in range(0,len(k)):
    for j in range(0,i):
        if k[i]>k[j] and dp[i]<dp[j]:
            dp[i]=dp[j]
 
    dp[i]+=1
 
 
print(max(dp))