7310 : 재귀 최장 공통 부분수열
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
두 문자열 $A$와 $B$의 최장 공통 부분수열(LCS: Longest Common Subsequence)의 길이와 LCS 문자열을 구하십시오.
LCS는 연속하지 않아도 되며, 두 문자열에 공통으로 나타나는 가장 긴 부분수열입니다.
탑다운 재귀(Top-down) + 메모이제이션 또는 바텀업 DP로 구현합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
LCS는 연속하지 않아도 되며, 두 문자열에 공통으로 나타나는 가장 긴 부분수열입니다.
탑다운 재귀(Top-down) + 메모이제이션 또는 바텀업 DP로 구현합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 문자열 $A$가 주어집니다. (길이 $\le 1{,}000$)
둘째 줄에 문자열 $B$가 주어집니다. (길이 $\le 1{,}000$)
둘째 줄에 문자열 $B$가 주어집니다. (길이 $\le 1{,}000$)
출력 설명
첫째 줄에 LCS의 길이를 출력합니다.
둘째 줄에 LCS 문자열을 출력합니다. (여러 개이면 아무 것이나)
둘째 줄에 LCS 문자열을 출력합니다. (여러 개이면 아무 것이나)
입력 예시
COPY
복사되었습니다!
복사되었습니다!
ABCBDAB
BDCAB
출력 예시
COPY
복사되었습니다!
복사되었습니다!
4
BCAB도움
dp[i][j]: $A[1..i]$와 $B[1..j]$의 LCS 길이. $A[i] = B[j]$이면 dp[i][j] = dp[i-1][j-1] + 1, 아니면 max(dp[i-1][j], dp[i][j-1]). 역추적으로 LCS 문자열을 복원합니다.