난이도 : 골드 4
유형 : DP , 역추적
https://www.acmicpc.net/problem/14002

문제

수열 A가 주어진다.
이 수열에서 가장 긴 증가하는 부분 수열(LIS)의 길이와,
그 중 하나를 실제로 구해 출력하는 문제다.

dp[i] = i번째 수를 마지막으로 하는 LIS의 길이 로 놓고
dp[i]를 계산하면서, 그 이전 인덱스 중에서 어떤 경로로 왔는지를 추적할 배열 prev[i]를 둔다.
마지막에 dp 배열에서 최댓값의 인덱스를 찾아 prev를 따라가며 수열을 복원한다.

해답 및 풀이

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

# dp[i] : i번째 원소를 마지막으로 하는 LIS(가장 긴 증가하는 부분 수열)의 길이
dp = [1] * n # 일단 모든 원소는 자기 자신만으로 길이 1인 LIS가 되니까 1로 시작
# prev[i] : i번째 원소가 포함된 LIS에서, 그 앞에 오는 원소의 인덱스
# (없다면 -1로 둔다)
prev = [-1] * n

# i번째 원소를 끝으로 하는 LIS를 구하기 위해
# i보다 앞에 있는 j를 모두 확인하면서 갱신
for i in range(n):
   for j in range(i):
       # arr[j] < arr[i]여야 증가하는 부분수열이 가능
       # dp[j] + 1 이 dp[i]보다 길다면 갱신
       if arr[j] < arr[i] and dp[i] < dp[j] + 1:
           dp[i] = dp[j] + 1
           prev[i] = j  # i번째 원소의 이전 원소를 j로 기록

# LIS의 최대 길이
length = max(dp)
print(length)

# LIS 수열 역추적
idx = dp.index(length)  # dp 값이 최대인 위치부터 추적 시작
sequence = []
while idx != -1:         # prev를 따라가면서 수열을 구성
   sequence.append(arr[idx])
   idx = prev[idx]

sequence.reverse()       # 거꾸로 모았으니 뒤집기
print(*sequence)