30805번 - 사전 순 최대 공통 부분 수열 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 9061 | 3053 | 2563 | 33.273% |
문제
어떤 수열이 다른 수열의 부분 수열이라는 것은 다음을 의미합니다.
- 해당 수열의 원소들이 다른 수열 내에서 순서대로 등장합니다.
- 예를 들어, $\{1,1,5\}$는 $\{3,\underline{\color{blue} 1} ,4,\underline{\color{blue} 1} ,\underline{\color{blue} 5} ,9\}$의 부분 수열이지만, $\{1,5,1\}$의 부분 수열은 아닙니다.
또한, 어떤 수열이 다른 수열보다 사전 순으로 나중이라는 것은 다음을 의미합니다.
- 두 수열 중 첫 번째 수가 큰 쪽은 사전 순으로 나중입니다.
- 두 수열의 첫 번째 수가 같다면, 첫 번째 수를 빼고 두 수열을 다시 비교했을 때 사전 순으로 나중인 쪽이 사전 순으로 나중입니다.
- 길이가 $0$인 수열과 다른 수열을 비교하면, 다른 수열이 사전 순으로 나중입니다.
양의 정수로 이루어진 길이가 $N$인 수열 $\{A_1,\cdots ,A_N\}$이 주어집니다. 마찬가지로 양의 정수로 이루어진 길이가 $M$인 수열 $\{B_1,\cdots ,B_M\}$이 주어집니다.
수열 $A$와 수열 $B$가 공통으로 갖는 부분 수열들 중 사전 순으로 가장 나중인 것을 구하세요.
입력
첫 줄에 수열 $A$의 길이 $N$이 주어집니다. $(1 \le N \le 100)$
둘째 줄에 $N$개의 양의 정수 $A_1,A_2,\cdots,A_N$이 주어집니다. $(1 \le A_i \le 100)$
셋째 줄에 수열 $B$의 길이 $M$이 주어집니다. $(1 \le M \le 100)$
넷째 줄에 $M$개의 양의 정수 $B_1,B_2,\cdots,B_M$이 주어집니다. $(1 \le B_i \le 100)$
출력
$A$와 $B$의 공통 부분 수열 중 사전 순으로 가장 나중인 수열의 크기 $K$를 출력하세요.
$K \ne 0$이라면, 다음 줄에 $K$개의 수를 공백으로 구분해 출력하세요. $i$번째 수는 $A$와 $B$의 공통 부분 수열 중 사전 순으로 가장 나중인 수열의 $i$번째 수입니다.
예제 입력 1
4 1 9 7 3 5 1 8 7 5 3
예제 출력 1
2 7 3
다음 수열들은 모두 $A$와 $B$의 공통 부분 수열입니다.
$$\begin{array}{cccc}\{\} & \{1\} & \{1,3\} & \{1,7\} \\\{1,7,3\} & \{3\} & \{7\} & \{7,3\} \\\end{array}$$
이 중 사전 순으로 가장 나중인 수열은 $\{7,3\}$입니다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호