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

카테고리 없음

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

minjiwoo 2022. 1. 25. 12:09

728x90

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

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

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}

www.acmicpc.net

n = int(input())
array = list(map(int, input().split()))

dp = [1]*n # 자기 자신 1개로도 길이가 1인 수열이 될 수 있으므로 1로 초기화를 해줍니다 !


for i in range(n):
    for j in range(i, n):
        if array[i] > array[j]: # 자기 자신보다 작은 원소일 때 
            dp[j] = max(dp[i]+1, dp[j]) # 원소를 포함할지 안할지 선택

print(max(dp))

728x90