[백준] 11053번 - 가장 긴 증가하는 부분 수열 (파이썬)

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

# 가장 긴 증가하는 부분 수열
import sys

N = int(input())
arr = list(map(int, sys.stdin.readline().split()))
dp = [1] * N

for i in range(1, N):
    for j in range(i):
        if arr[j] < arr[i]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

 

DP, LIS알고리즘

1. 2중 for문을 이용해서 (j < i)

    - dp(현재까지의 가장 긴 증가하는 부분수열의 길이)를 업데이트 해나간다

    - i 까지 이전의 dp를 이용해서 업데이트 해나가고 i를 하나씩 늘려가면서 다시 해나간다

2. dp의 값중 가장 큰 값을 출력

 

LIS(가장 긴 증가하는 부분 수열 알고리즘)

시간복잡도가 오래걸리는 DP버전이다