문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수열 A의 크기 N(1<= N <= 1,000,000)이 주어진다.
둘째 줄에는 수열 A을 이루고 있는 Ai가 주어진다.(-1,000,000,000 <= Ai <= 1,000,000,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.
일단 dp를 채우면서, dp에 저장된 원소의 순서가 arr 상에서 역순인지 아닌지를 파악하고
역순인 원소가 끼어있지 않은 경우에는 lis = dp[:],
역순인 원소가 끼어 있는 경우에는 체크하면서 관리하는 방법으로 해당 문제를 접근해 보았다.
그런데 이러한 방법은 위와 같은 문제가 있기 때문에 다른 방법을 찾아야 했다.
lis에서의 역추적
lis 알고리즘에서는 for문으로 arr를 원소 하나씩 순회하면서
해당 원소(arr[i])가 dp리스트에 추가(dp.append(arr[i])) or 갱신(dp[idx] = arr[i])되는 방식으로 진행된다.
path[i] : arr의 i번째 원소가 dp의 몇 번째 index에 추가 or 갱신되었는지 저장
일단 path = [-1 for _ in range(len(arr))]로 선언해 놓은 뒤,
lis 알고리즘을 진행하면서 dp 리스트를 추가 or 갱신할때,
path에 arr의 i번째 원소가 dp의 몇 번째 index에 추가 or 갱신되었는지 저장한다.
즉 arr 와 dp의 관계를 저장해 놓는다!
arr 순회를 마치고 lis 알고리즘이 종료되면, path에 저장된 값을 거꾸로 확인하면서 lis를 추출해 낸다.
import sys
from bisect import bisect_left
n = int(input())
arr = list(map(int,sys.stdin.readline().split()))
path = [-123 for _ in range(len(arr))]
dp = [arr[0]]; path[0] = 0
for i in range(1, len(arr)):
if dp[-1] < arr[i]:
dp.append(arr[i])
path[i] = len(dp)-1
else:
idx = bisect_left(dp, arr[i])
dp[idx] = arr[i]
path[i] = idx
l = len(dp)-1; lis = []
for i in range(len(arr)-1, -1, -1):
if path[i] == l:
lis.append(arr[i]); l -= 1
print(len(dp)); print(" ".join(map(str, reversed(lis))))