[알고리즘/DP] 11722번 : 가장 긴 감소하는 수 - python

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

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

---

• 문제
• 소요시간: 24분 22초

---

• 설계하기(접근방법) 

1. 입력받기

 

2. 구현하기

가장 긴 증가하는 부분수열을 거꾸로 하면 된다

가장 긴 감소하는 부분수열 = 가장 긴 증가하는 부분 수열을 뒤집은 것이고

우리는 수열의 길이를 구하면 되기 때문에 뒤집어서 풀어도 된다

 

리스트를 뒤집은 후

앞에서 부터 dp를 해준다

 

현재 숫자보다 작은 숫자 x 중에서

지금 자신 dp의 값보다 

크거나 같은 경우

dp[now] = dp[x] + 1 을 해준다

 

현재 dp가 1이고

자기 자신보다 작은 이전의 수의

이전 dp가 1이면

 

자신의 dp는 그 수+ 자신 포함할 수 있다는 의미이니

+1을 해주는 것이다

 

3. 출력하기

 

 

---

• 코드(출력)

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

num_list = num_list[:: -1]

## 10 20 20 10 30 10 자기보다 작은 수들 중의 dp[max]
dp = [1 for _ in range(n)] 

for i in range(n):
    for j in range(0, i):
        if num_list[i] > num_list[j]:
            if dp[j] >= dp[i]:
                dp[i] = dp[j] + 1

print(max(dp))

---

• 얻어갈 부분

1. 뒤집어서 겨우 아이디에이션 할 수 있었다. dp 문제의 경우 뒤집어서 접근해보자