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

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

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

 

코드

n = int(input())
num = list(map(int, input().split()))
dp = [1] * n

for i in range(1, n):
    for j in range(i):
        if num[i] > num[j]:
            # dp[i]에 저장되는 값 : num[i]를 마지막 값으로 가지는 가장 긴 증가부분수열의 길이
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

 

수열의 각 숫자들은

그 숫자 자체로 길이가 1인 증가부분수열임으로

dp 리스트를 전부 1로 초기화 해 주었다

 

dp 리스트의 dp[i]에 저장되는 값은

입력으로 들어온 수열을 저장한 리스트인 num 리스트에서

num[i]를 마지막 값으로 가지는 가장 긴 증가부분수열의 길이가 저장된다.

 

두 번째 수부터 마지막 수까지 순회를 하면서

각 수보다 인덱스가 작은 수들을 확인하고

인덱스가 작은 수가 현재 순회하고 있는 수보다 작을 경우에는

현재 순회하고 있는 수를 추가하여 더 긴 증가부분수열을 만들 수 있다는 의미임으로

j 인덱스까지의 증가부분수열의 길이에 1 더한 값들 중 최대 값을 dp 리스트에 저장한다.

 

따로 증가부분수열의 길이를 저장할 리스트 변수를 만들 수도 있지만,

dp 리스트에 저장을 하는 것이 더 메모리 효율적인 코드가 된다!

 

말로 설명한 내용을

그림으로 잘 설명해준 블로그가 있어 참고 자료에 링크를 첨부해둔다.

 

참고 자료

https://thingjin.tistory.com/entry/%EB%B0%B1%EC%A4%80-11053%EB%B2%88-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4-%ED%8C%8C%EC%9D%B4%EC%8D%AC