문제
자연수 N이 주어 졌을 때, 1부터 NxN으로 이루어져 있는 수열 X={x1, x2>, ..., xp, xp+1}와, 수열 Y={y1, y2, ..., yq, yq+1}가 주어질 때,
다음 조건을 만족 시키는 수열의 최대 길이를 구하는 프로그램을 작성하라.
조건은 다음과 같다.
● x1 = y1 = 1 이고, xp+1 = yq+1 = NxN 이다.
● 수열 내의 xi 값이 같은 것은 존재 하지 않으며, 역시 yi도 마찬가지이다.(여기서 i는 임의의 정수를 뜻한다.)
● X, Y 내의 원소들 중 임의의 원소들을 골라서 지운 다음, 입력 순서대로 정리했을 때, X, Y 내에서 같은 수열이 나온다면 이를 공통부분 수열이라고 한다.
● 우리가 구하고자 하는 수열은 이러한 공통부분 수열 중에서 1로 시작하여 NxN 으로 끝나는 최장 공통 부분 수열이다.
예를 들어 X={1,7,5,4,8,9}, Y={1,4,3,5,6,2,8,9}라고 할 때, 위의 조건을 만족 시키는 가장 긴 수열은 {1,4,8,9}이다.
수열 X, Y 가 주어졌을 때, 위의 조건을 만족하는 최대길이의 수열을 찾는 프로그램을 출력한다.
입력
첫 번째 줄에는 수열을 이루는 숫자의 범위를 나타내는 수 N(1<=N<=250)과, 각 수열의 길이를 나타내는 자연수 p,q(1 <= p,q < NxN)이 주어진다.
두 번째 줄에는 p+1개의 수열 X의 원소들이 수열 내의 순서대로 주어지며, 세 번째 줄에는 q+1개의 수열 Y를 이루는 Y의 원소들이 수열 내의 순서대로 주어진다.
수열 내에 중복되는 숫자는 없다고 가정하며, 수열내의 숫자는 1이상 NxN으로 이루어져 있다.
출력
입력된 수열에 대하여 조건을 만족 시키는 공통 부분 수열의 가장 긴 길이를 출력한다.
예제
3 6 7
1 7 5 4 8 3 9
1 4 3 5 6 2 8 9
4
로그인해야 코드를 작성할 수 있어요.