백준 14003 가장 긴 증가하는 부분 수열 5

문제

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

코드

n = int(input())

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

dp = [arr[0]]
index = [1]
for i in range(1, n):
    if dp[-1] < arr[i]:
        dp.append(arr[i])
        index.append(len(dp))
    else:
        low = 0
        high = len(dp)-1
        idx = 0
        while low <= high:
            mid = (low+high)//2
            if dp[mid] >= arr[i]:
                idx = mid
                high = mid-1
            elif dp[mid] < arr[i]:
                low = mid+1
        else:
            dp[idx] = arr[i]
            index.append(idx+1)
temp = len(dp)
print(temp)
result = []
for i in range(len(index)-1, -1, -1):
    if temp == index[i]:
        result.append(arr[i])
        temp -= 1

print(*list(reversed(result)))

풀이

dp 문제 가장 긴 증가하는 부분 수열입니다 이분탐색을 사용해서 O(nlogn)안에 문제를 풀어야 시간초과가 안나요

dp 테이블에는 현재 가장 긴 증가하는 부분 수열에서 최소값이 저장되어 있습니다

배열의 값이 저장된 인덱스를 따로 계산해서 부분 수열까지 출력을 해줬습니다