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

n = int(input())

n_list = list(map(int, input().split()))
dp = [1] * n
l = []
l.append(n_list[0])

for i in range(1, n):
    t = n_list[i]

    if t > l[-1]:
        l.append(t)
        dp[i] = len(l)
    else:
        start, end= 0, len(l)-1
        while start < end:
            mid = (start + end) // 2

            if l[mid] >= t:
                end = mid
            else:
                start = mid + 1
        l[start] = t
        dp[i] = start + 1
print(len(l))

tmp = len(l)
result = []
for i in range(n-1, -1, -1):
    if dp[i] == tmp:
        result.append(n_list[i])
        tmp -= 1

print(*result.reverse())

LIS의 시간복잡도인 O(n^2)로는 해결할 수 없는 문제
이 문제의 경우 이분탐색을 통해 풀어야 한다.

이분탐색 알고리즘을 사용해 풀어가면서 역추적도 해야하므로 수열 정보를 저장할 리스트도 필요하다.

이분탐색은 최대 값을 구하는것이 아니므로 Lower Bound 방식으로 한다.