[알고리즘/백준] 14002: 가장 긴 증가하는 부분 수열 4(python)

LIS를 구한 후
max_dp = 가장 긴 증가하는 부분 수열의 길이

max_idx = max_dp의 위치

l = 가장 긴 증가하는 부분 수열을 담을 리스트

이렇게 만들었다.

max_idx와 max_dp가 같으면 LIS에 해당하는 수이기 때문에 리스트에 추가해주고 max_idx와 max_dp를 1씩 빼주었다. max_idx를 빼는 이유는 하나씩 줄여가면서 max_dp와 같은 수를 찾기 위해서 이다.
max_dp를 빼주는 이유는 1개를 찾았으므로 찾아야하는 LIS의 길이가 1이 줄기 때문이다.

N = int(input())
a = list(map(int, input().split()))
dp = [1] * (N+1)
for i in range(N):
    for j in range(i):
        if a[i] > a[j]:
            dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))

max_dp = max(dp)
max_idx = dp.index(max_dp)
l = list()

while max_idx >= 0:
    if dp[max_idx] == max_dp:
        l.append(a[max_idx])
        max_dp -= 1
    max_idx -= 1
print(*reversed(l))