👩‍🎓공부 - 2024.02.06 소마대비 문제풀이

17216번 - 가장 큰 감소 부분 수열

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

import copy 
N = int(input())
lst = list(map(int,input().split()))
dp = copy.deepcopy(lst)

합의 최소는 자기 자신이므로 dp값은 기존 리스트 인덱스와 똑같이 초기화해줍니다.

for i in range(len(lst)):
    for j in range(i):
        if lst[i] < lst[j]:
            dp[i] = max(dp[i],dp[j]+lst[i])

각 인덱스마다 순회를 돌며 자기 자신보다 큰 인덱스가 존재하면 자기 자신의 dp값과 자기자신+큰 인덱스의 dp값 을 대조하여 더 큰 값을 넣어주도록 합시다.

print(max(dp))   

해당 dp값에서 제일 큰 값을 출력하면 됩니다.