백준python_가장긴최대부분증가수열3

It was so hard for me to understand any kinds of blogs
that dealt with this problem..

So I just followed the flow of consciousness ...

진짜 아무리 다른 블로그 읽어도 잘 이해안되서
의식의 흐름 기법대로
써봤다

import sys
sys.stdin = open("input.txt", "rt")
from collections import deque, Counter
sys.setrecursionlimit(100000)


'''
    우선, 우리가 여기서 무엇을 하려고 하는지를 잘 생각해야 한다.
    무슨 말이냐면,

    현재 num이라는 숫자를 만났다.
    우리는 num이 마지막에 올때의 최대 증가수열을 구하고 싶은 건데
    그럴려면, num보다 작은 수 중에서,
    최대증가수열을 지니는 애들 찾고, 거기에 + 1을 해줬었다.
    어디서 ? dp 방식에서 !!

    그런데, 생각해보니까, num보다 작은,
    즉, arr 중에서, num보다 작은 모든 애들을 다 탐색하면
    시간이 너무 오래걸린다.

    그래서 어떻게 해야할까. 고민을 하던 중 !
    매번, 특정 길이의 최대증가수열을 만들때,
    그때의 마지막 값이 무엇이었는지도 저장해두면 되지 않을까?

    예를 들어서, 어떤 배열 arr 가 있었다.
    arr 이라는 배열에서
    처음 값이 1이어서, 1이 마지막에 올때 , 만들어지는 최대 증가부분수열은 1이다 
    3, 4를 만났다.그러면,
    이전과 같이, 앞에서부터, 쭉 ~~ 검사하는 게 아니라

    어? 1이라는 값이 마지막에 올때, 최대 증가부분 수열이 길이가 1이었으니까
    당연히 3가 뒤에 붙으면 될것이고! 왜 ? 3는 1보다 크니까 !
    그러면 3이라는 숫자가 가장 마지막에 올 때, 만들어지는 최대 증가부분수열길이는 2 !

    마찬가지로 4를 만나면 !
    3보다 커서, 뒤에 붙고, 결국 3 !!

    어!! 그런데 이번에는 2를 만난거야.....
    2가 마지막에 올 때, 만들어지는 최대증가부분수열 길이....??
    2 ! 왜 ? 1 바로 뒤에 붙으면 되자나

    그런데, 아까 보니까, 3이 마지막에 올때도, 2였는데
    그러면 어떡하지 ?
    3을 2로 대체해주면 되지 !

    즉, 최대증가부분 수열 길이가 2일 때,
    마지막에 오는 값이, 3이 아니라, 2라는 거야 ! 

    그런데, 이렇게 update 시켜주는 이유는 뭐야 ?
    자. 지금까지의 과정을 정리하자면
    L 이라는 배열이 있다고 하자
    L[ i ]에서 i는 길이.
    그렇다면 L [ i ] 란 ?
    최대증가부분수열 길이가 i일때,
    그때 마지막으로 오는 수 !!

    이렇게 딱 L 이라는 배열에 다가,
    특정 숫자일때의, 최대증가부분 수열 정보를 저장해두면
    dp 에서와 같이, 앞에서부터 arr 배열을 쭉 ~ 검사하는 게 아니라,
    딱 L 이라는 배열만 보면 되는 거고,
    심지어 L 이라는 배열은, 오름차순 정렬이 되어 있기 때문에 ,
    이진탐색을 통해서, 내가 현재 arr 에서 만난 V 라는 값이,
    마지막에 올때,
    그때의 최대 부분 증가수열을 구할 때,
    그저 L에서, 자기 혹은, 자기와 가까우면서, 가장 큰, L [ i ] 를 찾고
    i 를 ,
    V 라는 값이 마지막에 올 때의, 최대 부분 증가수열 길이라고 setting 해주면 되는 것이다.
    그리고 L [ i ] 에다가 내가 만난 V 라는 정점으로 update 시켜주는 것이고,

    자. 여기서 중요한 것은
    L 이라는 배열은, 그저 참고용이지
    L 이라는 배열 자체가 최대부분 증가수열을 의미하는 것은 아니라는 점 ! 

    예를 들어보자 , 

    10 30 50 60이 생성되었고, 20이라는 숫자를 만났다면 ? 뒤에것을 다 날리는 건가 ?
    ex. 원래 arr >> 10 30 50 60 20 이었다면

    그렇다면 , 어떻게 ?? 30 자리에 들어가면 될까 ?
    10 30 50 60 에 "안" 들어가면 되는 거지

    ???
    L[i] 10  30  50  60
    i    1   2   3   4

    이렇게 저장되는 것인데,
    20을 만나면,
    L[i]를 탐색하면서 ,
    20 혹은, 20보다 큰 값을 찾는 것이다.

    왜 ?
    그것을 찾으면, 즉,
    20 혹은 20보다 큰 L[i]를 찾으면,
    i 가, 곧
    20으로 만들어지는 최대 증가부분 수열. 길이가 되는 것이므로 ! 

    보니까 30이,
    20보다 크거나 같은, 최소의 숫자.
    그리고 그것으로 만들어지는
    최대 부분 증가수열 길이는 2 !
    이제 update

    L[i] 10 20 50 60
    i    1  2  3  4

    하지만, 여전히 !
    최대부분 증가수열은
    10 30 50 60
    이 되는 것이지.

    그리고, 결국은 L의 최댓값을 출력하는 것이
    정답이 될 것이다.
    
    '''
def BS( st, ed, num ) :
    # num 보다 크거나 같은, 최소의 숫자를 찾아야 한다.
    while st < ed : # st와 ed가 같아지는 순간 그것이 정답
        mid = ( st + ed ) // 2
        if L[mid] == num :
            ed = mid
            break
        elif L[mid] < num :
            st = mid + 1
        elif L[mid] > num :
            ed = mid # 비록 지금 판단 상, L[mid]가 num보다는 크지만, 결국 num보다 크거나 같은
            # 최소의 숫자가 될 수 있으므로, 후보로 남겨두는 것이다.
    return ed
        
    
    

Len = map(int, input().split())
arr = list(map(int, input().split()))
L = []  # 증가하는 부분수열 !

for num in arr :
    if len(L) == 0 :
        L.append(num)
        continue
    if num > L[-1] :
        L.append(num)
    else:
        newIdx = BS( 0, len(L) - 1, num )
        L[newIdx] = num

print(len(L))