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

문제

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

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

---

코드

import sys
input = sys.stdin.readline

n=int(input())
a=list(map(int,input().split()))
dp = [1]*n // 모든 위치의 수열의 길이는 최소한 1이므로 dp를 1로 초기화

for i in range(n):
    for j in range(i): // i의 이전 위치를 모두 비교
        if a[i]>a[j] :
            dp[i] = max(dp[i],dp[j]+1) // 증가하는 수열이라면, dp 업데이트

print(max(dp)) // dp에서 가장 큰 값은 가장 긴 증가하는 부분 수열의 길이가 됨.

---

해설

• 주어진 수열에서 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)의 길이를 찾는 문제
• 모든 위치의 수열의 길이는 최소한 1이므로 dp 를 1로 초기화
• 이후 두 반복문을 사용해서 모든 위치 'i'에 대해 이전 위치 'j'를 비교합니다, a[i]가 a[j]보다 크다면 수열이 증가하고 있는 것이므로 dp[i]를 업데이트합니다.
• dp 배열에서 가장 큰 값은 가장 긴 증가하는 부분 수열의 길이가 됩니다.