백준 python 기록

백준 파이썬 11722 가장 긴 감소하는 부분 수열

작지 2021. 9. 13. 20:25

백준 링크: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())
s=list(map(int,input().split()))
dp=[1]*n
for i in range(1,n):
    for j in range(i):
        if s[i] < s[j]:
            dp[i] = max(dp[i],dp[j]+1)
print(max(dp))

dp중 간단한 문제라고한다. 난 아니었는데..

 

s[0],s[1]를 예시로 감소하지 않는 수이므로 if문의 조건에 맞지 않다.

s[1],s[2]를 예시로 30 , 10 이므로 감소하기때문에 max(dp[1],dp[2]+1)의 조건이 발동되어 [1,1,2,1,1,1]이 된다.

 

이렇게 반복하면 [1,1,2,2,2,3] 의 결과가 나오기떄문에 max(dp)를 출력하면 된다.