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

 

[ Contents ]

 

 

1. 문제 (링크 참조)

11055번: 가장 큰 증가 부분 수열

 

 

 

2. 문제 풀이

 가장 큰 '증가 부분 수열의 합'을 구하는 문제입니다. 

 

1, 5, 3, 20, 13, 100

 예를 들어, 위 수열에서 합이 가장 큰 증가 수열의 합은 1+3+20+100 = 124입니다.

 

 

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

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

 DP를 이용해야 합니다. 1부터 i번째까지의 최대 증가수열의 합을 구하면, i+1번째도 이전 계산값을 이용해서 빠르게 구할 수 있습니다. 

 'i번째 원소가 포함된 가장 큰 증가수열의 합'은 'i번째 원소보다 작은 이전 원소의 증가수열의 합 + i번째 원소' 입니다.

 

 

 

3. 코드

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

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