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

https://www.acmicpc.net/problem/11722
시간 1초, 메모리 256MB
input :

• N (1 ≤ N ≤ 1,000)
• Ai (1 ≤ Ai ≤ 1,000)

output :

• 수열 A의 가장 긴 감소하는 부분 수열의 길이

---

첫 시도.

리스트의 뒤에서 부터 비교를 하면 되지 않을까?

ㅡ ㅡ ㅡ ㅡ ㅡ [5개의 아이템이 존재할 때.]

ㅡ ㅡ 'ㅡ' ㅡ ㅡ
i 가 3이면.
j 가 4일 때, 5일 때 비교 해서 i 가 클 경우엔 감소하는 수열의 길이가 나오지 않을 까??

for i in range(n - 2, 0, -1):
    for j in range(i + 1, n):
        if data[i] > data[j]:
            dp[i] = max(dp[i], dp[j] + 1)

했는데 틀림.

두 번째.

어차피 감소하는 것도 수열 뒤집으면 증가하는 수열인데.
reverse() 해서 증가하는 부분 수열 구하는 함수로 구해버리자.

data.reverse()

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

정답 코드 :

import sys

n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
dp = [1] * n

data.reverse()

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

print(max(dp))