[🥇2 / 백준 12738 / 파이썬] 가장 긴 증가하는 부분 수열 3

 

12738번: 가장 긴 증가하는 부분 수열 3

 

문제

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

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

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 A_i가 주어진다. (-1,000,000,000 ≤ A_i ≤ 1,000,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

예제 입력 6 10 20 10 30 20 50

예제 출력 4

 

풀이

 

LIS의 역추적 문제이다.

가장 긴 증가하는 부분 수열 문제와 비슷하지만, 이번엔 N의 최대 길이가 1,000,000 으로 늘었다.

 

따라서 수열을 순회하며 나오는 숫자가 현재까지 만든 LIS의 마지막 숫자보다 작다면,

교체해줄 자리를 전부 탐색하는 것이 아닌 이분 탐색을 통해 시간복잡도를 O(NlogN)으로 줄여야 한다.

 

이분 탐색을 직접 구현해도 되지만, bisect 모듈을 사용하면 훨씬 더 쉽게 구현이 가능하다.

 

import bisect as bs

n = int(input())
nums = [0] + list(map(int,input().split()))
dp = [0]*(n+1)
# 문제의 조건에 음수가 포함되므로 최저를 0이 아닌 -무한대로 설정해준다.
cp = [-float('inf')]

for i in range(1, n+1):
    if nums[i] > cp[-1]:
        cp.append(nums[i])
        dp[i] = len(cp)-1
    else:
        dp[i] = bs.bisect_left(cp,nums[i])
        cp[dp[i]] = nums[i]
print(len(cp)-1)