[백준] 11053 : 가장 긴 증가하는 부분 수열 (Python)

정답코드

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int,input().split()))
dp = [1]*N
for i in range(N):
    m = A[i]
    for k in range(i):        
        if m > A[k]:
            dp[i] = max(dp[i], dp[k]+1)
print(max(dp))

아이디어💡

dp[i] : 인덱스 0부터 i까지 가장 긴 배열 길이

0부터 i-1까지 수 중에서, i번째 수보다 작은 수가 있으면 해당 배열 뒤에 i번째 수를 추가한다는 느낌(이 때 배열의 크기는 dp[k]+1)으로 dp[i] = max(dp[i], dp[k]+1)을 통해 dp[i]의 최댓값을 for k in range(i)동안 계속해서 업데이트해준다.

---

• 너무 쉽게 풀고 틀렸습니다가 나와서 내가 문제를 잘못 이해한건가 했다.

나와 같은 실수로 틀리는 사람을 위해 다음 예시를 첨부한다.
예시를 보면 이해할 수 있을 것이다.

100 1 2 101 3 4 5

내 처음 코드로 하면 100보다 큰 숫자가 101만 존재하므로 출력값이 2이다.
하지만 정답은 [1,2,3,4,5] 수열로 5가 나와야 한다.