문제
접근
LIS 알고리즘이다.
DP를 이용해서 풀 수 있지만, 이 방법은 O(n^2)이 걸린다.
DP[i] = i를 포함했을 때 최장 길이로, i 보다 작은 이전 수들 중에서 LIS가 가장 긴 곳에 +1을 하는 식이다.
이 문제는 입력값이 매우 크기 때문에 위의 방법을 이용하면 시간초과가 나온다.
이를 해결하기 위해 이분 탐색을 사용하여 LIS를 업데이트하는 방법을 사용했다.
최초에 arr[0]만 담겨있는 DP 배열을 하나 생성한다.
그리고 arr를 순서대로 보면서 DP[-1] 번째와 비교하여 더 크다면 DP에 현재 값을 append 해준다.
만약 더 작다면 DP 배열을 이분탐색하며 lower bound를 찾아준다.
찾은 위치를 해당 값으로 업데이트 한다.
정답은 DP 배열의 크기이다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split(' ')))
ans = [arr[0]]
def findLowerBound(item):
start = 0
end = len(ans) - 1
while True:
if start > end:
break
mid = (start+end)//2
if ans[mid] >= item:
end = mid-1
else:
start = mid+1
return start
for item in arr:
if item > ans[-1]:
ans.append(item)
else:
loc = findLowerBound(item)
ans[loc] = item
print(len(ans))