두 순열의 최장 공통 부분 수열

시간 제한2초메모리 제한512 MB

요약

1부터 N까지의 순열 두 개가 주어질 때, 두 순열의 최장 공통 부분 수열 길이를 구한다.

문제

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

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

1부터 $N$ 까지의 정수가 각각 정확히 한 번씩 등장하는 두 수열 $A$ 와 $B$ 가 주어진다. 두 수열의 LCS 크기를 구하는 프로그램을 작성하시오.

첫째 줄에 두 수열의 크기 $N$ ( $1 \le N \le 100{,}000$ )이 주어진다.

둘째 줄에 수열 $A$ 의 원소 $N$ 개가, 셋째 줄에 수열 $B$ 의 원소 $N$ 개가 공백으로 구분되어 주어진다.

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