문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, [1, 2, 3]과 [1, 3, 2]의 LCS는 [1, 2] 또는 [1, 3] 이다.

1부터 N까지 정수가 모두 한 번씩 등장하는 두 수열 A와 B가 주어졌을 때, 두 수열의 LCS 크기를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 수열의 크기 N (1 ≤ N ≤ 100,000)이 주어진다.

둘째 줄에는 수열 A에 들어있는 수가, 셋째 줄에는 수열 B에 들어있는 수가 주어진다.

출력

두 수열의 LCS의 크기를 출력한다.

풀이

처음 보고 에잉 쉽네 했는데 머리가 깨져버렸다.
https://chanhuiseok.github.io/posts/algo-34/
해당 글을 통해 lcs 구성방법을 읽어보았다.
원래는 LCS? substring인가? 그럼 보이어-무어 써도 되는 거 아닌가 생각했었는데 SubString이 아니라는 점때문에 보이어-무어 알고리즘이 아니라 LIS를 이용해야 했다.
글에서는 dp를 이용하지만 이분탐색을 이용해 해결하고 싶었다.

A와 B의 lis를 구성하고 순차 탐색으로 세는 방법도 고려해봤는데 A와 B의 lis가 다를 수도 있어서 실패했다.

결국 힌트를 보게되었는데, A를 참고하여 B를 통해 수열을 구성하는 것이었다.
정확히는 B의 i번째 인덱스가 A에서 어디에 위치하는지에 대해 알아내고, 이를 토대로 수열을 구성하는 것이다.
2250, 1365 와 유사한 문제였다.
A와 B간의 관계를 찾아내고, 최대한 많은 관계를 이어주면 되기 때문에 인덱스의 위치를 이용한 LIS 문제였던 것이다.

풀이는 쉬운데 생각하기 어려운 문제 유형이었다...

from bisect import bisect_left

input = open(0).readline

def lis(arr, N):
    k = []
    l_k = []
    for i in range(N):
        idx = bisect_left(k, arr[i])
        if idx == len(k): k.append(arr[i])
        else: k[idx] = arr[i]
        l_k.append(idx+1)
    return max(l_k)

N = int(input())

arr = []
A=dict()
for v, i in zip(map(int, input().split()), range(N)):
    A[v] = i
B = [*map(int, input().split())]
for i in range(N): arr.append(A[B[i]])

A_lis = lis(arr, N)
print(A_lis)

구에엑