[백준] 17216번 가장 큰 감소 부분 수열(feat. 다이나믹 프로그래밍, LDS)

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

 

문제 분석

• 첫 번째 단계 (문제 요약 및 조건 파악)

가장 큰 감소 부분 수열의 요소 합을 구하는 문제이다.
예를 들어

A = {1, 100, 2, 50, 60, 8, 7, 3, 6, 5}

인 경우에 가장 합이 큰 감소 부분 수열은 

A = {100, 60, 8, 7, 6, 5}

이다.

입력으로는 수열의 크기 N (1 <= N <= 1000)
수열을 이루는 Ai(1 <= Ai <= 1000)이 주어진다.

 

• 두 번째 단계(문제 핵심 파악)

LDS를 구하면서 DP테이블을 갱신하면 될 것이다.
DP테이블은 arr배열을 그대로 가져와서 초기화하면 될 것 이다.

 

코드 작성

import copy
import sys

n = int(sys.stdin.readline().rstrip())
arr = list(map(int, sys.stdin.readline().rstrip().split()))

dp = copy.deepcopy(arr)

result = 0
for i in range(n):
    for j in range(i):
        if arr[i] < arr[j]:
            dp[i] = max(dp[i], dp[j] + arr[i])

print(max(dp))

DP초기화와 갱신 로직이 핵심