[BOJ] 13711 - LCS 4 (Python)

 

 

아이디어

 

수열 A를 기준으로 수열 B의 인덱스를 정렬한 후 인덱스의 최장 증가 수열의 길이를 구한다.

 

 

풀이

 

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

solution()