백준 14003 파이썬 - 가장 긴 증가하는 부분 수열 5

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

14003번: 가장 긴 증가하는 부분 수열 5

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

코드

import sys
from bisect import bisect_left
length = int(sys.stdin.readline())
arr = [0] + list(map(int, sys.stdin.readline().split()))
dp = [0 for _ in range(length + 1)]
compare = [-1000000001]
maxNum = 0
for i in range(1, length + 1):
    if compare[-1] < arr[i]:
        compare.append(arr[i])
        dp[i] = len(compare) - 1
        maxNum = dp[i]
    else:
        dp[i] = bisect_left(compare, arr[i])
        compare[dp[i]] = arr[i]
print(maxNum)
result = []
for i in range(length, 0, -1):
    if dp[i] == maxNum:
        result.append(arr[i])
        maxNum -= 1
print(*(reversed(result)))

풀이

비슷한 다른 문제가 있지만 여기는 수의 범위가 커서 다른 방식으로 풀어야 했다.

메모이제이션을 통해 dp로 풀지만, 바이너리 서치가 합쳐진 형태이다. 이진 탐색은 compare리스트를 만들어 실행한다. 현재 배열 값이 이진 탐색 리스트의 가장 큰 값보다 크면 가장 긴 수열이 갱신되는 것이다. 만약 그렇지 않다면 현재 배열 값이 이진 탐색 리스트의 어디에 해당하는지 비교해서 값을 넣는다.