백준 / 14002 / 가장 긴 증가하는 부분 수열 / python

n = int(input())
n_list = list(map(int, input().split()))
dp = [1] * n

for i in range(n):
    for j in range(i, n):
        if n_list[j] > n_list[i]:
            dp[j] = max(dp[j], dp[i]+1)


tmp = max(dp)
print(tmp)
t_list = []
for i in range(n-1, -1, -1):
    if dp[i] == tmp:
        t_list.append(n_list[i])
        tmp -= 1

print(*t_list[::-1])

기존의 LIS 문제에서 그리디 알고리즘을 적용한 문제
가장 긴 증가하는 부분 수열을 앞에서부터(작은 수 부터)그대로 출력하게 되면 값이 전혀 다르게 나온다.

예를들어 수열 3 1 2에 대한 LIS 값은 1 1 2 이다. 그래서 앞에서 부터 출력하게되면 3, 2가 나오게된다.

따라서 뒤에서부터(큰 값부터) 저장하고 마지막에 역순으로 출력해주는 방식으로 정답을 구할 수 있다.