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

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

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

수열의 크기가 백만 단위라서 N^2 의 DP로는 문제로 풀 수 없다.

Binary Search를 활용해서 O(NlogN)으로 풀어낼 수 있다.

 

자세한 풀이는 

최적화된 LIS(Longest Increasing Subsequence) 알고리즘과 해 찾기

에서 확인할 수 있다.

 

	import sys
	import bisect
	n = int(sys.stdin.readline())
	arr = list(map(int, sys.stdin.readline().split()))
	table = [arr[0]]
	for idx in range(1, n):
	# 현재까지의 부분수열 최댓값보다 더 큰 값일 경우
	if arr[idx] > table[-1]:
	table.append(arr[idx])
	else:
	# 현재 값이 부분수열의 어느 부분에 해당하는지 - left idx로 확인
	insert_idx = bisect.bisect_left(table, arr[idx])
	# 해당 위치의 값 업데이트
	table[insert_idx] = arr[idx]
	# 최장 부분수열의 길이
	print(len(table))

view raw [백준] LIS_2.py hosted with ❤ by GitHub