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

문제

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

수열의 요소를 골라서 가장 긴 부분 수열을 만든 뒤, 그 수열의 길이를 출력하면 된다.

문제 풀이

dp[i] = 수열의 i번째 요소까지 만들 수 있는 가장 긴 배열의 길이 ( i >= 1 )

• 부분 수열의 값이 증가하지 않아도, 각 요소에 대한 배열의 길이는 1이다.
  따라서 dp의 모든 값을 1로 초기화 시켜준다.
  dp = [1] * n

• 이전의 수와 비교했을 때 증가하는 수열이면
  if nums[i] > nums[j]:
  dp[i]를 dp[j] + 1 중 가장 큰 값으로 바꿔준다.
  dp[i] = max(dp[i],dp[j]+1)

코드

import sys
input = sys.stdin.readline

n = int(input())
nums = list(map(int,input().rsplit()))
dp = [1] * n

# i = 0, j = 0
# i = 1, j = 0, 1 
# i = 2, j = 0, 1, 2 ...
for i in range(n):
    for j in range(i):
        if nums[i] > nums[j]:
            dp[i] = max(dp[i],dp[j]+1)

print(dp)