[DP] 백준 LIS 11053번 with Python3

 

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

11053번: 가장 긴 증가하는 부분 수열

문제

 

내 풀이

n = int(input())
sqnc = list(map(int, input().split()))

# dp = sqnc[i]를 마지막 원소로 가질 때 가장 긴 증가하는 부분 수열의 길이
dp = [1 for _ in range(n)]

for i in range(n):
    for j in range(i):
        if sqnc[i] > sqnc[j]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))

해설

주석 처럼 dp리스트는 sqnc의 i 번째 원소를 마지막 원소로 가질 때 가장 긴 증가하는 부분 수열의 길이를 dp[i]에 담는다.

 

1. sqnc[i] 를 기준으로 i 까지 for j 반복문을 돌려가며 진행된다.

2. sqnc[i] > sqnc[j]: 일 경우 dp[i]에 현재 dp[i] 값 과 dp[j] +1 값을 비교해  max 값을 넣는다.