12051 가장 긴 증가하는 부분 수열2

https://www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

알고리즘 분류

1. 이분탐색

 

아이디어

1. 최장길이 증가수열을 이분탐색으로 만듬

2. 최장길이 증가수열을 만드는 방법

- 리스트는 점점 증가하는 수로 앞부터 작은 수로부터 정렬하여 채움

- 가장 큰 수보다 더 큰수가 있으면 리스트 뒤에 추가

- 추가하는 수가 리스트의 가장 큰수보다 작으면 리스트에서 적절한 위치에 수를 위치해서 넣어줌 (맨 끝수가 더 작은수로 업데이트를 하는 것이 포인트라고 생각 -> 코드를 보면서 이해하면 빠름) ex. 10 20 40 30 35의 예시를 생각하면 리스트를 업데이트를 안해주면 10 20 40이고 업데이트를 하면 10 20 30 35로 업데이트가 가능함

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split(" ")))

    lis = [A[0]]

    for a in A[1:]:
        if lis[-1] < a:
            lis.append(a)
        else:
            low = 0
            high = len(lis) - 1
            while True:
                if low >= high:
                    break

                mid = (low + high) // 2

                if lis[mid] < a:
                    low = mid + 1
                else:
                    high = mid

            lis[high] = a

    print(len(lis))