[백준 17216번] 파이썬 - 가장 큰 감소 부분 수열

백준 17216 - 가장 큰 감소 부분 수열

시간 제한 1초, 메모리 제한 256MB

# 조건

• 수열 A가 주어졌을 때, 그 수열의 감소 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.
• 예를 들어, 수열 A = {1, 100, 2, 50, 60, 8, 7, 3, 6, 5} 인 경우에 합이 가장 큰 감소 부분 수열은 A = {1, 100, 2, 50, 60, 8, 7, 3, 6, 5} 이고, 합은 186이다.

입력

• 첫째 줄에 수열 A의 크기 N(1 ≤ N ≤ 1000)이 주어진다.
• 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다.(1 ≤ Ai ≤ 1,000)

출력

• 첫째 줄에 수열 A의 합이 가장 큰 감소 부분 수열의 합을 출력한다.

# 접근 방법

• dp를 이용하여 풀어주면 된다.
• dp의 초기값은 입력받은 nums 배열을 깊은 복사해준다.
• 2중 반복문을 돌리며 결과를 누적시켜 dp값을 갱신시켜주면 된다.
  • 처음꺼는 N까지
  • 2번째는 i까지 돌려주며
    • nums[j] 가 nums[i]보다 크다면 dp[i] = max(dp[i], dp[j] + nums[i]) 로 갱신해준다.

import sys  
sys.stdin = open('input.txt')  
si = sys.stdin.readline  

N = int(si())  
nums = [*map(int, si().split())]  
dp = [i for i in nums]  

for i in range(N):  
    for j in range(i):  
        if nums[j] > nums[i]:  
            dp[i] = max(dp[i], dp[j] + nums[i])  
print(max(dp))