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

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

아이디어

arr[i]가 가질 수 있는 최대의 길이를 d[i]에 기록해 나간다. 첫 번째 인덱스부터 i-1번째 인덱스까지 탐색하며 가장 길이가 길면서 arr[i]보다 작은 값을 가지는 원소를 찾는다.

코드

N = int(input())
arr = list(map(int, input().split()))
arr.insert(0, 0)
d = [0]*(N + 1)

for i in range(1, N + 1):
    tmp = 0
    for j in range(i):
        if tmp < d[j] and arr[j] < arr[i]:
            tmp = d[j]
    d[i] = tmp + 1

print(max(d))

여담

이렇게 풀면 시간복잡도가 O(N^2)이다. 이 방법으로는 입력 크기가 1,000,000인 12015번 문제를 풀 수 없다. 다른 방법을 생각해내야 한다 !