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

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

---

풀이

11053 가장 긴 증가하는 부분 수열과 비슷한 문제지만, 가징 긴 증가하는 부분 수열 중 하나를 출력해야 한다는 점이 추가되었다. 때문에 부분 수열을 저장하는 자료 구조가 더 필요하다.

pre_index_table이라는 리스트를 추가해 증가하는 부분 수열의 이전 인덱스를 저장하게끔 만들었다. 가장 긴 증가하는 부분 수열의 길이를 구했으면 그 수열의 인덱스로 pre_index_table을 계속 참조하게끔 만들었다.

부분 수열의 길이를 구하는 방법은 11053 가장 긴 증가하는 부분 수열과 방법이 동일하다

코드

# Initial
N = int(input())
A = list(map(int, input().split()))
answer_arr = []
answer_len = 0

# Make dp table
dp = [1 for _ in range(N)]
pre_index_table = [i for i in range(N)]
for i in range(N):
    arr = list()
    for j in range(i):
        if A[i] > A[j]:
            # dp[i] = max(dp[i], dp[j] + 1)
            if dp[i] > dp[j] + 1:
                dp[i] = dp[i]
            elif dp[i] < dp[j] + 1:
                dp[i] = dp[j] + 1
                pre_index_table[i] = j

answer_len = max(dp)
target = dp.index(answer_len)
# 이전 인덱스 탐색
for _ in range(answer_len):
    # print("[DEBUG] now target:", target)
    answer_arr.insert(0, A[target])
    target = pre_index_table[target]

# Answer
print(answer_len)
print(' '.join(map(str, answer_arr)))