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

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

14002번: 가장 긴 증가하는 부분 수열 4

---

풀이 과정

https://greentea31.tistory.com/34

백준 11053 - 가장 긴 증가하는 부분 수열 [파이썬]

 

위 문제에서 사용했던 식 D[i] = max(D[J]) + 1 (j < i, A[j] < A[i])으로 가장 긴 증가하는 부분 수열의 길이는 구할 수 있었지만, 이번 문제는 부분 수열 그 자체를 구해야 한다.

 

이를 위해서는 S[i] 배열을 하나 더 만들어서 D[i]를 계산할 때 쓰인 max(D[j])에서 max일때 쓰인 j를 저장하도록 하자. 그러면 가장 긴 증가하는 부분 수열의 길이가 가장 긴 D[i]에서 S 배열을 확인하면서 부분 수열의 index를 뒤에서 부터 확인할 수 있고, 이를 뒤집어서 출력해주면 가장 긴 증가하는 부분 수열 자체를 구할 수 있다.

 

예시는 다음과 같다.

---

소스 코드

import sys

N = int(sys.stdin.readline())

A = list(map(int, sys.stdin.readline().split()))
A.insert(0, 0)

d = [1 for _ in range(N+1)]
s = [0 for _ in range(N+1)]

for i in range(2, N+1):
    checkMaxLength = 0
    for j in range(1, i):
        if A[j] < A[i]:
            if checkMaxLength < d[j]:
                checkMaxLength = d[j]
                s[i] = j
    d[i] = checkMaxLength + 1

maxIndex = 0
maxValue = 0
for i in range(1, N+1):
    if maxValue < d[i]:
        maxValue = d[i]
        maxIndex = i

print(maxValue)
n = maxIndex
answer = []

while True:
    answer.append(A[n])
    n = s[n]
    if n == 0:
        break

answer.reverse()
print(' '.join(str(i) for i in answer))