[백준][이진탐색][LIS] 12015. 가장 긴 증가하는 부분 수열 2

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

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

 

 

• 풀이
  • 가장 긴 증가하는 부분 수열의 길이를 구하는 문제
  • N (1 ≤ N ≤ 1,000,000)이기 때문에
    • 11055. 가장 큰 증가하는 부분 수열 N (1 ≤ N ≤ 1,000)  처럼 2중 for문 돌면서 DP 로 풀면 시간 초과남
    • 굳이 N개의 수들에 대해서 현재 위치 이전의 모든 수를 반복하며 훑어봐야할까?
  • dp [i]를 구하기 위해 dp[0]~dp[i-1]의 최댓값을 알고 있다면 반복하지 않아도 된다!
    • -> python의 bisect

bisect.bisect_left( dp, num[i]) : dp가 정렬되어있다는 가정하에 num[i]값이 들어갈 위치 반환

-> dp의 왼쪽부터 탐색을 시작해서, num[i]보다 크거나 같은 원소를 처음으로 만났을 때의 인덱스를 반환한다

 

• 1. dp를 arr[0]으로 초기화한다.
• 2. 현재 위치(i)가 이전 위치의 원소들보다 크면 dp에 추가한다.
• 3. 현재 위치(i)가 이전 위치의 원소보다 작거나 같으면, bisect.bisect_left로 이전 위치의 원소 중 가장 큰 원소의 index값을 구한다. 그리고 dp의 index 원소를 arr[i]로 바꿔준다.
  • -> 실제 LIS는 아니지만 "길이" 값 만큼은 조건을 만족

 

import bisect
n=int(input())
num=list(map(int,input().split()))
dp=[num[0]]
for x in num:
    if dp[-1]<x:
        dp.append(x)
    else:
        i=bisect.bisect_left(dp,x)
        dp[i]=x

print(len(dp))