[python] 백준 11722 가장 긴 감소하는 부분 수열

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

11722번: 가장 긴 감소하는 부분 수열

 

 

문제 해결

수열에서 부분 수열 중 감소 수열이 되도록 뽑았을 때 가장 긴 수열을 찾는 문제

n번째 수는 뽑힐 수도 있고 안 뽑힐 수도 있음

n번째 수가 뽑힌다고 가정할 때 n-1번까지 수열중 가장 긴 수열에 +1이 되는 것이며 마지막 수보다 n번째 수가 작아야한다.

n번째 수를 넣었을 때 가장 긴 수열을 dp[n]이라고 하고 문제를 풀어보자.

 

CODE

import sys
input = sys.stdin.readline
INF = sys.maxsize
n = int(input())
A = [INF]+list(map(int, input().split()))
dp = [0 for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(i):
        if A[j] > A[i]:
            dp[i] = max(dp[i], dp[j]+1)
print(max(dp[1:]))

 

유사문제

https://thought-process-ing.tistory.com/68

[python] 백준 11055 가장 큰 증가 부분 수열