📌 [BOJ] 백준 12015 가장 긴 증가하는 부분 수열 2

📖 문제

📖 예제

📖 문제

from bisect import bisect_left

N = int(input())
A = list(map(int, input().split()))

LIS = [A[0]]

for i in A:
  if LIS[-1] < i:
    LIS.append(i)
  else:
    LIS[bisect_left(LIS, i)] = i

print(len(LIS))

4번째 푸는거라고 하는데 전혀 기억나지 않았다. . .
dp 방식으로 풀면 간단하지만 시간복잡도의 제약이 있기 때문에 이진 탐색으로 분류되는 문제이다.
bisect_left()를 활용하면 비교적 쉽게 풀리는 문제이다.