[BOJ] 14002번 - 가장 증가하는 부분 수열 4

---

문제설명

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

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

사고과정

• 아무거나 수열 출력하는 부분에서 매우 고생했다.. 오히려 문제의 난이도가 여기에서 올라가는 것 같다.. 반례에 자꾸 걸려서 구글링을 했는데 구글링한 것 중에서도 간결한 코드를 찾기가 쉽지 않았다. 그러던 중 하나의 훌륭한 블로그 글을 발견하고! 해당 풀이를 참조했다!(감사합니다 :) 

풀이(스스로 못 푼 풀이)

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

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

max_length = max(dp)
print(max_length)
result = []
for i, length in enumerate(dp[::-1]):
    if length == max_length:
        result.append(array[n-1 - i])
        max_length -= 1
print(*result[::-1])