백준_python 11053번 가장 긴 증가하는 부분 수열 (DP)

<문제 링크>

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

 

<정답 코드>

 sol ) 다이나믹 프로그래밍으로 가장 긴 증가하는 수열 구하기

n = int(input())
a = list(map(int, input().split()))
 
dp = [0 for _ 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(i, dp)
    
print(max(dp))

line 6 ) 배열 a의 i번째 원소를 기준으로

line 8 ) i번째 원소가 j번째 원소들보다 크고(=증가하는 수열) and dp[i]가 현재까지의 가장 긴 수열 길이(dp[j])보다 작으면

line 9 ) dp[i]에 dp[j]값 대입해 증가하는 수열 길이 갱신

 

line 11의 주석을 해제하고 i 와 dp 를 출력한 결과

 

dp[i]는 배열 a의 i번째 요소까지의 증가하는 수열의 길이