[Python][백준/BOJ] 11722번 : 가장 긴 감소하는 부분 수열

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

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

 

내 코드

import sys
input = sys.stdin.readline

n= int(input())
arr = list(map(int, input().split()))
dp = [1 for i in range(n)]

for i in range(n):
    for prev in range(0, i):
        if arr[prev] > arr[i]:
            dp[i] = max(dp[prev]+1, dp[i])
print(max(dp))

 

DP 감소.ver

이제 가장 긴 감소하는 부분 수열, 가장 긴 증가하는 부분 수열은 완벽하게 마스터한 것 같다.

3분만에 풀었다!

dp를 1로 초기화해주고, 수열을 보면서 이전 수보다 작은지 확인한다.

작다면 평행세계인 dp에도 1씩 올려준다. (cnt의 의미)

그리고 가장 긴 수열의 길이이므로 max(dp)하면 결과값이 출력된다.

 

비슷한 문제 풀이

https://beehand.tistory.com/83

[Python][백준/BOJ] 14002번 : 가장 긴 증가하는 부분 수열 4

 

https://beehand.tistory.com/82

[Python][백준/BOJ] 11053번 : 가장 긴 증가하는 부분 수열