12015번: 가장 긴 증가하는 부분 수열 2
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
from bisect import bisect_left
n = int(input())
arr = list(map(int, input().split()))
d = []
for i in arr:
k = bisect_left(d, i)
if len(d) <= k:
d.append(i)
else:
d[k] = i
print(len(d))
|
cs |
수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 {10, 20, 30, 50}
if :
d 에 현재 값을 append
else:
해당 인덱스의 값을 더 작은값으로 최신화
https://jason9319.tistory.com/113 설명이 잘 되어있으니 참고
'알고리즘 문제풀이 with 파이썬 > 백준' 카테고리의 다른 글
| [1713번, 구현] 후보 추천하기 (0) | 2021.09.11 |
|---|