파이썬 알고리즘 229번 | [백준 11053번] 가장 긴 증가하는 부분 수열 - DP - 다시풀어

229. 가장 긴 증가하는 부분 수열

1) 어떤 전략(알고리즘)으로 해결?

• DP

2) 코딩 설명

<내 풀이>

import sys

n = int(sys.stdin.readline().rstrip())
nlis = (list(map(int, sys.stdin.readline().rstrip().split())))
dp = [1 for _ in range(n+1)]

for i in range(1,n) : # 내가 지금 수열에서 만난 숫자 
    for j in range(i) : # 나보다 앞에 있던 애들 
        if nlis[i] > nlis[j] : # 나보다 작은 애를 만나면, 걔 뒤에서 내가 이어질 수 있으므로 그때 비교 
            dp[i] = max(dp[i], dp[j]+1)
# print(dp)
print(max(dp))

< 틀렸던 풀이>

import sys

n = int(sys.stdin.readline().rstrip())
nlis = (list(map(int, sys.stdin.readline().rstrip().split())))
dp = [1 for _ in range(max(nlis)+1)]

for i in range(1,n) : # 내가 지금 수열에서 만난 숫자 
    for j in range(i) : # 나보다 앞에 있던 애들 
        if nlis[i] > nlis[j] : # 나보다 작은 애를 만나면, 걔 뒤에서 내가 이어질 수 있으므로 그때 비교 
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))

• 인덱스 에러

<반성 점>

• 문제를 잘못 이해했어서 많이 헤맸던 점이 아쉬운 부분이다~

<배운 점>