시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 512 MB 547 241 (44%) 215
문제
부분 수열(Subsequence)은 어떤 수열에서 순서를 유지하되, 그 중 일부 항만을 선택하여 만들 수 있는 수열이다. 예를 들어, $(1, 3, 2, 4)$로 이루어진 수열이 있다면, $(1, 3, 4)$, $(1, 2, 4)$등은 부분 수열이 될 수 있지만, $(1, 2, 3)$은 부분수열이 될 수 없다. 최장 공통 부분 수열(Longest Common Subsequence)은 여러 개의 수열 모두에서 공통으로 등장하는 부분 수열 중 가장 긴 부분 수열을 의미한다. 예를 들어, 수열 $(1, 3, 2, 4)$와 $(1, 4, 2, 3, 4)$의 최장 공통 부분 수열은 주어졌을 때 최장 공통 부분수열은 $(1, 3, 4)$ 혹은 $(1, 2, 4)$가 된다. 수열의 각 항을 문자 하나로 생각하면, 문자열에 대해서도 최장 공통 부분 수열을 정의할 수 있다. 두 개의 문자열이 들어왔을 때 최대 공통 부분 수열의 길이를 알아내자.
입력
첫 번째 줄에 문자열 $A$가 주어진다. 두 번재 줄에 문자열 $B$가 주어진다. 주어지는 문자열은 대문자로만 이루어지고, 길이는 $1$ 이상 $1,000$ 이하이다.
출력
문자열 $A$와 $B$의 최장 공통 부분 문자열의 길이를 출력한다
힌트
#### 예제 입력 ``` ACGTGCCT AGGTCC ``` #### 예제 출력 ``` 5 ```