최장 공통 부분 수열 (LCS)

문제 설명

두 문자열이 주어졌을 때, 두 문자열의 최장 공통 부분 수열(Longest Common Subsequence)의 길이를 구하세요.

부분 수열이란 원래 문자열에서 일부 문자를 삭제하여 만들 수 있는 문자열입니다. 단, 남은 문자들의 순서는 유지되어야 합니다.

입력 형식

첫 줄: 문자열 A

둘째 줄: 문자열 B

출력 형식

LCS의 길이

제약 조건

• 1 ≤ |A|, |B| ≤ 1,000
• 문자열은 알파벳 대문자로만 구성

예시 설명

ACAYKP와 CAPCAK의 LCS는 ACAK로 길이가 4입니다.