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

문제📖

풀이🙏

• 가장 긴 증가하는 부분 수열은 다음 포스팅을 통해 구하는 법을 참고한다.
• 가장 긴 증가하는 부분 수열에 해당하는 값들을 알기위해서 x 값에 dp의 최대값을 저장한다.
• dp[i]에 해당하는 값이 x랑 같으면 i번째 데이터를 result 리스트에 추가한다.
• 마지막으로 result 리스트를 reverse 시켜 증가하는 부분 수열에 속하는 data 값을 출력한다.

코드💻

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

for i in range(len(data)):
    for j in range(i):
        if data[j] < data[i]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))
x = max(dp)

result = []
for i in range(n-1, -1, -1):
    if dp[i] == x:
        result.append(data[i])
        x -= 1
result.reverse()
for r in result:
    print(r, end=' ')