[백준] 12015. 가장 긴 증가하는 부분 수열 2 - Python

[Gold II]

 

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

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

 

풀이

이분 탐색(Binary Search)를 이용해, log(n logN)의 시간 복잡도로 풀어내는 LIS 문제.

 

res 배열을 생성,

입력된 배열을 모두 순회하며, res 배열의 마지막 숫자보다 크다면 res 맨 뒤에 append.

작다면, 이분 탐색을 이용해 들어갈 자리를 찾고, 그 index에 대신 삽입.

최종적으로 LIS의 길이를 구할 수 있게 된다.

다만 이렇게 만들어진 배열이 항상 LIS인 것은 아니니, 주의.

 

AC.

import bisect
n = int(input())

lines = list(map(int, input().split()))

res = []
for i in lines:
    a = bisect.bisect_left(res, i)
    if a == len(res):
        res.append(i)
    else:
        res[a] = i
        
print(len(res))