면접

면접 대비

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

요약

두 수열 a와 b가 주어질 때, a의 부분수열이면서 b의 부분수열이기도 한 가장 긴 증가 부분수열의 길이를 구합니다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 배열
정답자: 아직 제출이 없습니다

문제

Sasnart 회사의 입사 면접에서 지원자는 두 수열의 최장 공통 증가 부분 수열 문제를 푼다.

수열 $a_i$ 에서 부분 수열 $a_{i_k}$ 를 골라야 하며, 이 부분 수열은 다음 조건을 모두 만족한다.

증가한다. 즉 모든 $k$ 에 대해 $a_{i_k} < a_{i_{k+1}}$ 이다.
수열 $b_i$ 의 부분 수열이다.
위 두 조건을 만족하는 모든 수열보다 길이가 짧지 않다.

입력

첫째 줄에 두 정수 $n$ 과 $m$ 이 주어진다 ( $1 \le n, m \le 5,000$ ). 두 정수는 각각 수열 $a_i$ 와 $b_i$ 의 길이이다. 둘째 줄에는 $a_i$ 를 이루는 $n$ 개의 자연수가, 셋째 줄에는 $b_i$ 를 이루는 $m$ 개의 자연수가 주어진다. 모든 수는 10,000을 넘지 않는다.

출력

조건을 만족하는 수열의 길이를 나타내는 정수 하나를 출력한다.

예제1

예제 1
입력
```
6 5
2 3 1 4 6 5
1 2 5 4 6
```
예상 출력
```
3
```