자연수 N이 주어 졌을 때, 1부터 NxN으로 이루어져 있는 수열 X={x₁, x_2>, ..., x_p, x_p+1}와, 수열 Y={y₁, y₂, ..., y_q, y_q+1}가 주어질 때,

다음 조건을 만족 시키는 수열의 최대 길이를 구하는 프로그램을 작성하라.

조건은 다음과 같다.

● x₁ = y₁ = 1 이고, x_p+1 = y_q+1 = NxN 이다.

● 수열 내의 x_i 값이 같은 것은 존재 하지 않으며, 역시 y_i도 마찬가지이다.(여기서 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 가 주어졌을 때, 위의 조건을 만족하는 최대길이의 수열을 찾는 프로그램을 출력한다.

최장 공통 부분 수열 timer 1s memory 64MB

최장 공통 부분 수열 1s 64MB