|
from bisect import bisect_left
n = int(input())
l = list(map(int, input().split()))
table = [l[0]]
for i in range(1, n):
if l[i] > table[-1]:
table.append(l[i])
else:
table[bisect_left(table, l[i])] = l[i]
print(len(table))
|
수열의 원소의 range는 +-10억으로 넓어졌지만, 수열의 길이는 12015와 마찬가지로 1,000,000이다
이분탐색을 이용한 대소비교에는 문제가 없으므로 12015와 같은 코드(https://uneducatedjungler.tistory.com/47)로도 시간 안에 제출할 수 있다.
'Week 01 ~ 04 : 알고리즘 문제 풀이' 카테고리의 다른 글
| 파이썬 백준 14003 가장 긴 증가하는 부분 수열 5 (0) | 2021.11.17 |
|---|---|
| 파이썬 백준 14002 가장 긴 증가하는 부분 수열 4 (0) | 2021.11.17 |
| 파이썬 백준 12015 가장 긴 증가하는 부분 수열 2 (0) | 2021.11.17 |
| 파이썬 백준 11722 가장 긴 감소하는 부분 수열 (0) | 2021.11.17 |
| 파이썬 백준 11053 가장 긴 증가하는 부분 수열 (0) | 2021.11.16 |