[BOJ] 14003 - 가장 긴 증가하는 부분 수열 5 (Python)

 

 

아이디어

 

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

 

 

풀이

 

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

solution()