다이나믹 프로그래밍 - 백준 14002 [Python]

Problem)

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

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

Solution)

가장 긴 증가하는 부분 수열 문제이다.

부분 수열은 수열에서 수를 선택해서 만드는 수열이다.

 

이때, 수열에 있던 수의 순서는 변경할 수 없다.

 

수열의 길이가 N일 때, 선택 가능한 수는 2^N이 된다. (왜냐하면 그 수를 선택하거나, 안하거나 둘중 하나기 때문이다.)

이때, 모든 부분 수열을 만드는 것은 불가능하기 때문에 다이나믹으로 해결한다.

 

D[i] = A[i]를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이로 둔다. 이때 A[i] 이전의 수는 i이전의 어떤 수 이기 때문에 A[j]라고 표시하고 j<i 조건을 만족해야 하고, A[j] < A[i]여야 한다.

 

D[i] = max(D[j] + 1) 이고 시간복잡도는 O(N^2)이 된다.

 

이때, 어떤 값인지까지 출력해야하므로 V[i]를 선언하여 A[i]의 앞에 와야하는 수의 인덱스를 저장하도록 한다.

 

Answer)

n = int(input())
a = list(map(int,input().split()))
d = [0]*(n)
v = [-1]*(n)
    
for i in range(n):
    d[i] = 1
    for j in range(i):
        if a[j] < a[i] and d[j]+1 > d[i]:
            d[i] = d[j] + 1
            v[i] = j
ans = max(d)
print(ans)

p = [i for i,x in enumerate(d) if x == ans][0]
def go(p):
    if p == -1:
        return
    
    go(v[p])
    print(a[p], end=' ')
    
go(p)
print()