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

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

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

 

 

# 조건

• 수열 A가 주어졌을 때 가장 긴 증가하는 부분 수열을 구하라

 

# 접근 방법

• 이전의 하위 문제처럼 DP를 이용하여 이전 값들을 모두 순회한다면 수열 A의 크기 1,000,000 이하 이므로 시간초과가 난다.
• 따라서, 현재 값들을 dp테이블에 추가해주며, dp에서 가장 큰 수보다 크다면 append, 아니라면 들어갈 수 있는 자리를 찾아서 넣어준다.
• 찾는 모듈은 bisect를 이용해준다.

import sys, bisect  
input = sys.stdin.readline  
  
  
N = int(input())  
arr = [*map(int, input().split())]  
  
dp = [arr[0]]  
  
for i in range(N):  
  
    if arr[i] > dp[-1]:  
        dp.append(arr[i])  
    else:  
        idx = bisect.bisect_left(dp, arr[i])  
        dp[idx] = arr[i]  
  
print(len(dp))