[Python]백준 - 11053 : 가장 긴 증가하는 부분 수열

문제

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

 

풀이

나의 풀이

수열 A를 역순으로 탐색해, 최솟값이 갱신될때마다 부분 수열의 개수를 1씩 늘리는 방법 고안

하지만, 최솟값이 갱신되지 않더라도 부분 수열의 개수는 증가할 수 있음

 

다른 풀이

# 가장 긴 증가하는 부분 수열
n = int(input())
nums = list(map(int, input().split()))
dp = [1]*n

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

 

앞으로 DP 문제를 더 많이 풀어봐야겠다.