백준 11055번 가장 큰 증가 부분 수열 파이썬

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

11055번: 가장 큰 증가 부분 수열

 

내 답안

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))

dp = [0] * N
dp[0] = A[0]

for i in range(1, N):
    for j in range(i):
        if A[i] > A[j]:
            dp[i] = max(dp[i], A[i] + dp[j])
        else:
            dp[i] = max(dp[i], A[i])

print(max(dp))

---

 

DP는 정말 많이 공부 해야겠다..

점화식 세우는게 생각보다 헷갈렸다.

입력이

10
1 100 2 50 60 3 5 6 7 8  일때 내가 원하는 dp 는 [1, 101, 3, 53, 113, 6, 11, 17, 24, 32] 이다.

이건 정확하게 식을 세웠지만

계속 답이 틀려서 반례를 생각해 보았다.

 

입력이

6
10 20 10 30 20 50  일때 내가 원하는 dp 는 [10, 30, 10, 60, 30, 110] 이다.

하지만 dp 가 [10, 30, 0, 60, 30, 110] 이 나왔다.

 

이유는 14번째 줄에

else:
    dp[i] = max(dp[i], A[i])

if 문에 A[i] ≤​ A[j] 일 경우를 따로 생각을 안해서이다.

A[i] > A[j] 가 아니라면 dp는 자기 자신이나, 지금까지의 dp 값을 현재 dp 값으로 지정해 줘야 한다.