[Baekjoon 11722] 가장 긴 감소하는 부분 수열 | Python

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

---

문제

 

주어진 수열의 부분 수열 중 가장 긴 감소하는 수열을 찾는 문제이다.

 

---

풀이

 

각 인덱스에서 감소하는 수열의 최대 길이를 확인하고 그 중 가장 큰 값을 출력하면 된다.

어떤 인덱스를 i라 하면 에서 감소하는 수열의 최대 길이는 i보다 앞 인덱스의 수 중 num[i]보다 큰 수를 찾고, 그 중 그 인덱스의 감소하는 수열의 최대 길이를 확인하여 1을 더하면 i에서의 감소하는 수열의 최대 길이가 된다.

예제로 주어진 아래 수열을 확인해보자.

10 30 10 20 20 10

10은 자신보다 앞에 수가 없으므로 0에서의 감소하는 수열의 최대 길이는 1이다. 30 역시 자신보다 앞에 수 중 자신보다 큰 수가 없으므로 1이다. 10은 앞 수 중에 30이 자신보다 큰데, 30의 인덱스인 1에서 감소하는 수열의 길이가 1이므로 10, 즉 인덱스가 2인 곳에서 감소하는 수열의 최대 길이는 2이다. 이런식으로 각 인덱스에서 감소하는 수열의 최대 길이를 확인할 수 있다.

 

---

코드

 

num_n = int(input())
num = list(map(int, input().split()))
decrease = [1] * num_n
for i in range(1, num_n):
    for j in range(i):
        if num[i] < num[j]:
            decrease[i] = max(decrease[i], decrease[j]+1)
print(max(incre))