[백준 🥇4] 14002번 가장 긴 증가하는 부분 수열 4 (Python/파이썬)

1️⃣ 문제

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

2️⃣ 코드

유명한 DP 문제인 LIS 문제 시리즈

n = int(input())
arr = list(map(int, input().split()))

dp = [[] for _ in range(n)]
for i in range(n):
    dp[i].append(arr[i])

for i in range(1, n):
    for j in range(i):
        if arr[j] < arr[i]:
            if len(dp[j]) + 1 > len(dp[i]):
                dp[i] = dp[j] + [arr[i]]

answer = []
for i in range(n):
    if len(dp[i]) > len(answer):
        answer = dp[i]

answer.sort()   # 처음에 dp에 arr의 각 원소를 넣어 초기화 시켜줬기 때문에 정렬을 다시 해줘야 함
print(len(answer))
print(' '.join(map(str, answer)))

이 문제 풀이 검색해보면 대부분 수열의 길이 먼저 구하고 역추적해서 수열 구하는 방식으로 풀었던데 나는 한꺼번에 구하는 방식으로 풀었다