[DP/동적계획법] 백준 14002 가장 긴 증가하는 부분 수열 4 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

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

 

 

 

2. 문제 풀이

 가장 긴 증가 수열을 찾는 문제입니다. 중간에 작은 숫자가 끼어 있어도 무시할 수 있습니다.

 

2022.04.12 - [Algorithm] - [DP/동적계획법] 백준 11053 가장 긴 증가하는 부분 수열 - 파이썬(Python)

 가장 긴 증가 부분 수열을 찾는 방법은 위 문제에서 찾았습니다. 해당 부분은 위 링크를 참조해주세요. 이 문제에서는 추가로, '수열'을 출력해야 합니다.

 수열은 계산한 캐시값을 역추적해서 구할 수 있습니다.

 

 

 

3. 코드

# 입력
N = int(input())
A = list(map(int, input().split()))

# DP로 가장 긴 증가 부분 수열 찾기
cache = [1]*N
for i in range(N):
    for j in range(i):
        # 더 작은 이전 원소 발견
        if A[i] > A[j]:
            # 이전 원소에 +1한 게 더 길면 갱신
            cache[i] = max(cache[i], cache[j]+1)
res = max(cache)
print(res)

 DP를 이용해서 가장 긴 증가 부분 수열을 찾아줍니다. i번째 가장 긴 증가 수열은 'i보다 작은 이전 원소까지의 가장 긴 증가 수열 + 1'로 갱신할 수 있습니다. 이를 N번째까지 구해준 후, 계산한 캐시 중 가장 긴 길이를 출력합니다.

 

 

# 역추적
array = [] # 증가수열
for i in range(N-1, -1, -1):
    if cache[i] == res:
        array.append(A[i])
        res -= 1

for i in array[::-1]:
    print(i, end=" ")

 이후 역추적해서 수열을 찾아줍니다. 만약 가장 긴 길이가 5라면, 캐시가 5인 원소를 찾습니다. 이후 캐시가 4인 원소, 3인 원소... 로 되짚어 올라갑니다.

 캐시 값을 찾을 때, i보다 작은 이전 원소까지의 길이에 1(자기 자신)을 추가했습니다. 반대로 역추적할 때는 자기 자신인 1을 빼가면서 자기 자신을 반환합니다.