[백준] 14002 가장 긴 증가하는 부분 수열4

📖 문제

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

💻 내 코드

import sys

n = int(sys.stdin.readline())
nums=list(map(int, sys.stdin.readline().split()))

dp = [1]*n

for i in range(n-1):
    for j in range(i+1, n): # 현재 수 뒤를 탐색
        if nums[j]>nums[i]: # 현재 수보다 더 큰 수가 나오면
            dp[j]=max(dp[i]+1, dp[j]) # dp리스트에서 현재까지 나온 수와 새로 더한 수중 최댓값 저장

m=max(dp)
print(m)
idx = dp.index(m)
res=[]
for i in range(idx, -1, -1): # 가장 큰 수부터 거꾸로 탐색해 나간다
    if dp[i]==m:
        res.append(nums[i])
        m-=1

res.reverse()
for i in res:
    print(i, end=' ')

💡 풀이

• 먼저 가장 긴 증가하는 부분 수열의 길이를 구한다
• 현재 수와 그 뒤의 수를 계속해서 비교했을 때 자신보다 큰 수가 뒤에 나오면 1을 더해준다
• 마지막까지 비교하고 나면 dp배열에서 가장 큰 수가 가장 긴 증가하는 부분 수열의 길이가 된다
• dp 배열에서 가장 큰 수의 인덱스와 같은 인덱스의 원래 배열의 수가 수열에서 가장 큰 수가 된다는 것을 알 수 있다
• 그 수부터 거꾸로 수열의 길이를 하나씩 줄이면서 탐색
  • 그 인덱스에 해당하는 수가 수열의 다음수(거꾸로 했을때)가 된다
• 거꾸로 찾았으므로 다시 배열을 뒤집어서 출력해주면 된다