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

문제

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

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

풀이

n = int(input())
numbers = list(map(int,input().split()))
memo = [0]*n

for i in range(n):
    target = [0]
    for j in range(i):
        if numbers[j] < numbers[i]:
            target.append(memo[j])
    memo[i] = max(target)+1
print(max(memo))

DP 문제이고 타뷸레이션 방식을 사용하였다.

memo[i]에 저장된 값은 i번째 까지의 수열에서 가장 긴 증가하는 부분수열의 길이이다.

i미만의 수 j에 대해서 j번째 수가 i번째 수보다 작으면 memo[j]를 후보에 추가하고, 최종적으로 후보들 중 가장 긴 길이 +1을 하여 memo[i]에 저장해주는 방식이다.

i가 4일때 반복문 내부에서 실행되는 코드

 

가장 긴 증가하는 부분수열에 관한 다른 문제들도 많았는데 나중에 풀어서 올리도록 하겠다.