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

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다

 

코드

N = int(input())
A = list(map(int, input().split()))
A1 = [None]*N
for i in range(N):
    k = 0
    for j in range(i):
        if A[j]<A[i] and A1[j]>k:
            k = A1[j]
    A1[i] = k+1

print(max(A1))

 

풀이

수열 A의 k번째 원소에 대해, k까지의 가장 긴 증가하는 부분 수열의 길이는 1~k-1번째 원소들에 대해서 이들 중

 (1) 해당 순서의 원소가 A의 k번째 원소보다 작고,

 (2) 각 원소까지의 가장 긴 증가하는 부분 수열

의 길이의 최댓값에 1을 더했다고 볼 수 있다.

따라서 A의 1번째 원소부터 각 원소까지의 가장 긴 증가하는 부분 수열의 길이를 구해가는 문제로 바꿀 수 있을 것이다. 동적 계획법을 이용해서 이 부분 수열의 길이들을 하나의 배열에 또다시 저장한다면, 이들의 최댓값이 원하는 최대 길이가 된다. 이때 시간 복잡도는 O($n^2$)가 된다.