[백준][DP] 11053번 가장 긴 증가하는 부분 수열 python (200922)

www.acmicpc.net/problem/11053

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

 

1. 문제 설명 

 

 

 

2. 풀이 

 

n = int(input())
a = list(map(int, input().split()))
dp = [0 for i in range(n)]
for i in range(n):
    for j in range(i):
        if a[i] > a[j] and dp[i] < dp[j]:
            dp[i] = dp[j]
    dp[i] += 1
print(max(dp))

 

여기서도 DP 를 활용하고 이중 for 문을 쓰면 된다. 

여기서 DP[index] 에는

a[index] 의 숫자 이전에 나온 수 중에서 a[index] 보다 작은 수를 센 값이 여기 들어간다 

 

10 20 10 30 20 50 이면

 1    1    1   3    2   4

 

그리고 여기서 가장 큰 값이 해당 리스트에서 가장 큰 값이 부분 수열 길이가 되는 것 

 

 

 

** 참고 링크 

 

 

bitwise.tistory.com/215

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

wootool.tistory.com/96

[백준][11053번][DP] 가장 긴 증가 부분 수열