[Python/Baekjoon] 11055. 가장 큰 증가 부분 수열

💬 문제

문제 난이도: 백준 실버 2

문제 링크: https://www.acmicpc.net/problem/11055

❗️접근 방법

• 백준 11053과 굉장히 유사한 문제 (11053에 대한 나의 풀이)
• 단지 구해야 하는 것이 길이에서 크기로 바뀌었다.
• 따라서 dp리스트를 [1 for _ in range(N)]으로 초기화했던 것과 달리
• dp리스트를 입력으로 받은 A리스트를 깊은 복사했다.
• 가장 긴 증가 부분 수열의 최솟값(최소 길이)이 자기자신만을 포함한 1이였다면
• 가장 큰 증가 부분 수열의 최솟값은 자기자신의 값이기 때문이다.
  

✅ 정답 코드

# 가장 큰 증가 부분 수열
import sys, copy
input = sys.stdin.readline
print = sys.stdout.write

N = int(input())
A = list(map(int, input().split(' ')))
dp = copy.deepcopy(A)
for i in range(1, N):
    for j in range(i):
        if A[i] > A[j]:
            dp[i] = max(dp[i], dp[j]+A[i])
print(f'{max(dp)}')