[ BOJ 11055 ] 가장 큰 증가 부분 수열(Python)

문제

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

배열에서 특정 숫자들을 빼면 증가 수열이 된다.
그 증가 수열들 중 가장 합이 큰 수열을 구하는 문제다.

문제 풀이

증가 부분 수열에 대해서 찾아보는데에 시간이 더 걸렸던 것 같다.
나무위키 에 설명이 굉장히 잘되어있다!

증가 부분 수열
몇 개의 수를 제거해서 오름차순으로 정렬된 수열

배열 dp[i]에는 arr[i]를 가장 큰 값으로 가지는 증가 부분 순열의 합을 넣어줄 것이다.

만약 비교값 arr[j] 이 현재값arr[i] 보다 작고 (;증가 수열이고),
(비교값을 마지막 값으로 갖는 수열의 합 + 현재값) 이 현재 수열의 값보다 크면,
현재 수열의 값을 갱신해준다.

for i in range(1,n+1):
    for j in range(1,i):
        # 증가 수열 & 현재 순열의 합보다 크면 갱신 
        if arr[i] > arr[j] and dp[j] + arr[i] > dp[i]:
            dp[i] = dp[j] + arr[i]
    
    # 최대값을 저장해준다.
    if memo < dp[i]:
        memo = dp[i]

코드

import sys
input = sys.stdin.readline

n = int(input().rstrip())
arr = ['dummy']
dp = ['dummy']
# dp[i] = arr[i]를 가장 큰 값으로 가지는 수열의 합

nums = input().rstrip().rsplit()
for num in nums:
    arr.append(int(num))
    dp.append(int(num))

memo = 0

for i in range(1,n+1):
    for j in range(1,i):
        # 증가 수열 & 현재 순열의 합보다 크면 갱신 
        if arr[i] > arr[j] and dp[j] + arr[i] > dp[i]:
            dp[i] = dp[j] + arr[i]
    
    if memo < dp[i]:
        memo = dp[i]

print(memo)