[BOJ] 2352 - 반도체 설계 (Python)

 

 

아이디어

 

이분 탐색으로 최장 증가 부분 수열의 길이를 구한다.

 

 

풀이

 

def solution():
    n = int(input())
    numbers = tuple(map(int, input().split()))
    LIS = [numbers[0]]
    cnt = 1
    for i in range(1, n):
        if numbers[i] > LIS[-1]:
            LIS.append(numbers[i])
            cnt += 1
        else:
            s = 0
            e = cnt-1
            while s <= e:
                m = (s+e)//2
                if LIS[m] > numbers[i]:
                    e = m-1
                elif LIS[m] < numbers[i]:
                    s = m+1
                else:
                    LIS[m] = numbers[i]
                    break
            else:
                LIS[s] = numbers[i]
    print(cnt)

solution()