11053 - 가장 긴 증가하는 부분 수열

 

---

 

문제

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

11053번: 가장 긴 증가하는 부분 수열

 

 

풀이

이 문제에서 n의 제한은 1000이다. 따라서 O(n^2) 풀이가 가능한것을 인지하고 있자.

 

증가하는 수열이므로, 특정 인덱스 앞의 요소들을 하나씩 다 살펴본다.

1) 이후 만약 값이 나보다 작고

2) 해당 값에 저장된 수열 + 1 (현재 인덱스까지 포함하면 + 1 이니까 ) , 현재 수열의 길이를 비교해서 크다면 갱신해준다.

 

 

코드

l = int(input())
arr = list(map(int, input().split()))
d = [1] * 1001
for i in range(l):
    for j in range(i):
        if arr[j] < arr[i]:
            d[i] = max(d[j]+1, d[i])

print(max(d))

 

후기

DP 문제니까 무조건 O(n)에 가까운 시간복잡도로 끝내야한다고 생각하고, 이중 for문을 처음에 사용할 생각을 하지 않았다. 제한이 1000 이라는것에 다시 한 번 유의하자..