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

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

12015번: 가장 긴 증가하는 부분 수열 2

문제

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

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

코드

import sys
from bisect import bisect_left
a = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
dp = [0]
for i in arr:
    if dp[-1] < i:
        dp.append(i)
    else:
        dp[bisect_left(dp, i)] = i
sys.stdout.write(str(len(dp) - 1))

풀이

bisect_left는 리스트에서 i라는 원소가 들어갈 가장 왼쪽 위치를 반환해주는 함수이다. 가장 마지막 원소가 현재 원소보다 작으면 뒤로 이어서 붙여주면 되고, 아닌 경우에는 이진탐색으로 해당 인덱스의 원소를 교체해주면 된다.