[DP/동적계획법] 백준 11053 가장 긴 증가하는 부분 수열 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

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

 

 

 

2. 문제 풀이

 가장 긴 증가 수열을 찾는 문제입니다. 단, 중간에 작은 원소가 있어도 무시할 수 있습니다.

 

10 20 10 30 20 50

 예를 들어, 위 수열의 '가장 긴 증가 수열'은 [ 10, 20, 30, 50 ] 입니다.

 

 

2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

[Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

 가장 긴 증가수열을 구하기 위해서, 이전까지의 증가수열 길이를 저장해둬야 합니다.

 'N번째 원소가 포함된 가장 긴 증가수열의 길이'는 'N번째 원소보다 작은 이전 원소의 길이 + 1'입니다. 이를 비교하면서 가장 긴 증가수열을 찾아야 합니다.

 

 

 

3. 코드

#입력
N = int(input())
A = list(map(int, input().split()))

#DP
cache = [1]*N
for i in range(N):
    for j in range(i):
        # 더 작은 이전 원소 발견
        if A[i] > A[j]:
            # 이전 원소에 +1한 게 더 길면 갱신
            cache[i] = max(cache[i], cache[j]+1)
print(max(cache))