[Python] 백준 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이다.

 

풀이설계

• 리스트에서 val을 하나씩 꺼내온다.
  • dp[-1]는 보다 val이 크다면 뒤에 바로 추가해준다.
  • 그렇지 않다면 이분탐색(bisect_left)을 이용하여 어디에 추가할지 인덱스를 정하고 val을 추가한다.

import sys
from bisect import bisect_left


input = sys.stdin.readline
n = int(input())
lst = list(map(int, input().split()))
dp = [0]

for val in lst:
    if dp[-1] < val:
        dp.append(val)
    else:
        dp[bisect_left(dp, val)] = val

print(len(dp)-1)