이번 문제는 DP를 이용하여 해결하였다. 증가하는 부분 수열의 길이는 구하기 쉬웠지만, 수열을 구하는 과정에서 시간이 걸렸다. 우선 dp리스트를 2중 for문을 통해 순회하며 자신보다 앞에 있는 수 중 자신이 더 클 경우 dp를 갱신하였다. 이렇게 되면 증가하는 수열에 해당하는 dp의 값만 증가한다. 이 과정이 끝나면 기준값을 dp리스트의 최댓값으로 선언하고, dp리스트를 뒤에서부터 순회하며 기준값과 같은 경우에 결과 리스트에 수를 담고, 기준값을 감소시켜가며 진행하였다. 그리고 결과 리스트를 거꾸로 출력하였다.

Code

n = int(input())
arr = list(map(int, input().split()))
dp = [1 for _ in range(n)]
for i in range(1, n):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j]+1)
answer = max(dp)
ans_list = []
std = answer
for i in range(n-1, -1, -1):
    if dp[i] == std:
        std -= 1
        ans_list.append(arr[i])
print(answer)
print(*ans_list[::-1])