백준 / 가장 긴 증가하는 부분 수열 4 / 14002번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 가장 긴 증가하는 부분 수열 4 / 14002번 (골드 4단계)

문제 사이트: https://www.acmicpc.net/problem/14002

 

문제 설명

---

나의 풀이

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=' ')

---

※ 알아야 할 것

https://www.acmicpc.net/problem/12015 이 문제랑 다르다.

이 풀이는 1번째 코드에서 수열이 증가하면 증가하는 길이만큼 출력한다.

그리고 그 최대 증가하는 수들은 x 값을 가지고 있을 테니깐 뒤에서부터 x 값과 같은 수를 result에 넣고 오름차순으로 정렬해서 하나씩 출력했다.