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

🤔문제 해결

• S2 | DP

참고(비슷한 유형) : deok2kim.tistory.com/173

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

numbers에는 수열이 들어있다.

dp라는 1차원 리스트를 만든다. (1초 초기화, 감소하는 부분 수열의 길이가 들어갈 것이다.)

1로 초기화한 이유는 혼자만 가능할 때는 길이가 1이므로

 

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

자신보다 앞쪽의 숫자가 클 경우 - 나와 그 숫자는 감소하는 부분 수열이다.

그렇다면 앞쪽의 숫자의 부분 수열의 길이에 1을 더한 값이 자신의 부분 수열의 길이이다.

각 숫자에서 가장 긴 숫자를 dp 에 저장한다.

max값을 출력

 

💻소스 코드

N = int(input())
numbers = list(map(int, input().split()))

dp = [1] * N

for i in range(1, N):
    for j in range(i):
        if numbers[j] > numbers[i]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))
 

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

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

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