-
Notifications
You must be signed in to change notification settings - Fork 0
/
12015.py
35 lines (29 loc) · 1.71 KB
/
12015.py
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
30
31
32
33
34
35
# coding: utf-8
"""
난이도 : 7
문제 : 첫째 줄에는 1이상 백만 이하의 정수가 주어지고, 다음줄에 그 개수만큼의 수열(수의 나열)이 주어진다. 수열 역시 1~100만 정수. 출력은 가장 긴 증가하는 부분수열의 길이를 출력한다. 여기서 부분수열은, 띄엄띄엄도 가능이다.
아래예제에서 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
알고리즘 : 핵심 원리 : bisect_left를 이용해 순서가 있는 수열에 대해, 주어진 수를 알맞은 위치에 넣는 것.
주어진 수열을 A에 넣고, 결과리스트 dp=[]를 정의한다.
A를 for문으로 반복하며, 각 num에 대해 dp에 들어갈 알맞은 위치 k를 정한다. (k는 dp의 인덱스)
k에 대해 경우에 따라 2가지 행동을 한다.
1. k가 dp의 맨 오른쪽일 때 (len(dp) == k)
이 때는, num이 dp에서 최대값이라는 것이다. → dp.append(num)
2. 그 외에는 num이 dp에서 최대값이 아니라는 것이고, 그 값을 알맞게 바꿔야 한다.
dp[k] = num 을 통해, 알맞은 위치(k)에 num을 대치한다.
→ 대치 하지 않으면, num보다 크고, dp[k]보다 작은 수를 놓친다.
예를 들어, 10, 20, 15, 17, 20 순서라고 하자.
num이 15일때 dp는 [10, 20]으로 for문을 시작한다. k는 1일 것이다. 조건문 이후에
20을 15로 대치해야, 다음 for문에서 17을 놓치지 않는다.
"""
from bisect import bisect_left
N=int(input())
A=list(map(int,input().split()))
dp=[]
for num in A:
k = bisect_left(dp,num)
if len(dp) == k:
dp+=[num]
else:
dp[k]=num
print(len(dp))