7018 : 문자열 편집 거리 (삽입·삭제만)
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 1
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 줄에 걸쳐 두 소문자 문자열이 주어질 때, 문자 삽입(Insert)과 삭제(Delete) 연산만을 사용하여 한 문자열을 다른 문자열로 변환하는 데 필요한 최소 편집 거리(Edit Distance)를 구하는 프로그램을 작성하시오. (대체 연산은 허용되지 않는다.)
[제약 조건]
• 데이터 쌍 수 $N$: $1 \le N \le 20$
• 각 문자열의 길이: $1 \le |S| \le 100$ (소문자 알파벳)
[제약 조건]
• 데이터 쌍 수 $N$: $1 \le N \le 20$
• 각 문자열의 길이: $1 \le |S| \le 100$ (소문자 알파벳)
입력 설명
첫째 줄에 데이터의 개수 주어진다. 둘째 줄부터 줄에 두 개의 소문자 문자열이 공백으로 구분되어 주어진다. ($1 \le N \le 20$, 각 문자열의 길이 $\le 100$)
출력 설명
각 줄별로 두 문자열 사이의 최소 편집 거리를 한 줄에 하나씩 출력한다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3
abcde abdfe
hello world
abc xyz
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2
8
6도움
대체 연산이 허용되지 않는 경우, 두 문자열의 최소 편집 거리는 (A) + len(B) - 2 imes LCS\_len(A, B) 같다. DP(최장 공통 부분 수열)를 이용해 구한다.