(Python/파이썬) 백준 11722번 - 가장 긴 감소하는 부분 수열

문제출처: https://www.acmicpc.net/problem/11722

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

1. 코드

n = int(input())
arr=list(map(int, input().split()))
 
dp=[1]*n
 
for i in range(n):
    for j in range(i):
        if arr[j] > arr[i]:
            dp[i]= max(dp[i],dp[j]+1)
 
print(max(dp))

2. 해결과정

arr 안의 수에 대해서 가장 긴 감소하는 부분 수열의 길이를 구해주면 되는 문제이다.

arr를 하나씩 돌면서 자신보다 앞의 숫자와 비교한다.

1) 자신보다 앞의 숫자가 큰 경우 : 나와 앞의 숫자는 감소하는 부분 수열

-> 앞 숫자의 부분수열의 길이에 1을 더해주면 자신의 부분 수열 값이 나온다.

 

각 숫자에서 가장 긴 숫자를 dp에 저장

dp의 max값을 출력해준다.