아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

사전 순 최대 공통 부분 수열

시간 제한1초메모리 제한1024 MB

요약
길이 100 이하인 두 양의 정수 수열의 공통 부분 수열 가운데 사전 순으로 가장 뒤인 것을 찾는다.
난이도

보통10점 중 6점

유형
동적 계획법, 그리디, 문자열, 완전 탐색
정답자
아직 제출이 없습니다

문제

어떤 수열이 다른 수열의 부분 수열이라는 것은 다음을 의미합니다.

  • 해당 수열의 원소들이 다른 수열 내에서 순서대로 등장합니다.
  • 예를 들어, 1,1,5\\{1,1,5\\}는 3,1‾,4,1‾,5‾,9\\{3,\underline{\color{blue} 1} ,4,\underline{\color{blue} 1} ,\underline{\color{blue} 5} ,9\\}의 부분 수열이지만, 1,5,1\\{1,5,1\\}의 부분 수열은 아닙니다.

또한, 어떤 수열이 다른 수열보다 사전 순으로 나중이라는 것은 다음을 의미합니다.

  • 두 수열 중 첫 번째 수가 큰 쪽은 사전 순으로 나중입니다.
  • 두 수열의 첫 번째 수가 같다면, 첫 번째 수를 빼고 두 수열을 다시 비교했을 때 사전 순으로 나중인 쪽이 사전 순으로 나중입니다.
  • 길이가 00인 수열과 다른 수열을 비교하면, 다른 수열이 사전 순으로 나중입니다.

양의 정수로 이루어진 길이가 NN인 수열 A_1,⋯ ,A_N\\{A\_1,\cdots ,A\_N\\}이 주어집니다. 마찬가지로 양의 정수로 이루어진 길이가 MM인 수열 B_1,⋯ ,B_M\\{B\_1,\cdots ,B\_M\\}이 주어집니다.

수열 AA와 수열 BB가 공통으로 갖는 부분 수열들 중 사전 순으로 가장 나중인 것을 구하세요.

입력

첫 줄에 수열 AA의 길이 NN이 주어집니다. (1≤N≤100)(1 \le N \le 100)

둘째 줄에 NN개의 양의 정수 A_1,A_2,⋯ ,A_NA\_1,A\_2,\cdots,A\_N이 주어집니다. (1≤A_i≤100)(1 \le A\_i \le 100)

셋째 줄에 수열 BB의 길이 MM이 주어집니다. (1≤M≤100)(1 \le M \le 100)

넷째 줄에 MM개의 양의 정수 B_1,B_2,⋯ ,B_MB\_1,B\_2,\cdots,B\_M이 주어집니다. (1≤B_i≤100)(1 \le B\_i \le 100)

출력

AA와 BB의 공통 부분 수열 중 사전 순으로 가장 나중인 수열의 크기 KK를 출력하세요.

K≠0K \ne 0이라면, 다음 줄에 KK개의 수를 공백으로 구분해 출력하세요. ii번째 수는 AA와 BB의 공통 부분 수열 중 사전 순으로 가장 나중인 수열의 ii번째 수입니다.

예제1

  1. 예제 1

    입력
    4
    1 9 7 3
    5
    1 8 7 5 3
    
    예상 출력
    2
    7 3