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

haruponea·2021년 4월 7일
0

BOJ

목록 보기
39/41

문제 링크https://www.acmicpc.net/problem/14002

풀이
가장 긴 증가하는 부분 수열을 구하는 문제는 유명한 dp문제인데 여기서 묻고자 하는 것은 dp의 경로를 추적할 수 있느냐? 라는 것입니다. dp의 경로를 저장하기 위한 pre배열을 만들었습니다. pre[i] = j 라는 것은 i번째 숫자를 포함하는 가장 긴 증가하는 부분 수열을 구했을 때 바로 전 숫자는 j번째에 있습니다 라는 의미입니다. dp를 실행하면서 dp[i]가 가장 큰 i를 구해야 하는데 그 i는 start_idx에 저장했습니다. 그후 start_idx를 따라 추적하면서 역순으로 출력하면 됩니다.

python

import sys
input = sys.stdin.readline
n = int(input())
nums = list(map(int, input().split()))
dp = [1]*(n+1)
pre = [-1]*(n+1)
maxn, start_idx = 1, 0
for i in range(n):
    for j in range(i):
        if nums[j] < nums[i]:
            if dp[i] < dp[j] + 1:
                dp[i] = dp[j]+1
                pre[i] = j
                if maxn < dp[i]:
                    maxn = dp[i]
                    start_idx = i
trace = []
print(maxn)
while True:
    if start_idx == -1:
        break
    trace.append(nums[start_idx])
    start_idx = pre[start_idx]
print(*trace[::-1])

0개의 댓글