[백준] 11054 "가장 긴 증가하는 부분 수열" -python

알고리즘

 다이나믹 프로그래밍 기법을 통해  i번째 요소를 포함하여 최대길이인 지점을 저장한 뒤 dp중 최댓값을 출력한다.

또한,  최소 길이는 1이므로 dp의 값을 1로 초기화한다.

 

소스코드

# 가장 긴 증가하는 부분 수열
import sys
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

dp = [0] + [1] * n

for i in range(1, n+1):
    for j in range(1, i):
        if arr[j-1] < arr[i-1]:
            dp[i] = max(dp[i], 1 + dp[j]) # i번째 요소까지 최대 길이
            
print(max(dp))

 

느낀점

 dp를 무작정 0으로 초기화했고 맨 뒤에 값을 출력한다고 생각해서 오답이 나왔다. 내가 정의한 dp는 우선 i번째 요소를 포함하여 i번째 까지중 최대 길이를 저장한 것이고 조건에 만족되지 않는 길이중 더 큰 길이의 수열이 있을 수 있으므로 무작정 맨뒤에 값을 출력하는게 답이 아니다.