8034 : 편집 거리
•시간제한: 3.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
두 문자열 $A$와 $B$가 주어집니다. 문자열 $A$에 다음과 같은 3가지 연산을 적용하여 문자열 $B$로 변환하려고 합니다.
1. 문자 삽입: 임의의 위치에 문자 하나를 삽입합니다.
2. 문자 삭제: 임의의 위치의 문자 하나를 삭제합니다.
3. 문자 대체: 임의의 위치의 문자 하나를 다른 문자로 바꿉니다.
문자열 $A$를 $B$로 만드는 데 필요한 최소 연산 횟수(최소 편집 거리, Levenshtein Distance)를 구하는 프로그램을 작성하시오.
[제약 조건]
• 테스트 케이스 수 $T$
• 각 문자열의 길이는 $1$ 이상 $2{,}000$ 이하의 알파벳 대문자입니다.
1. 문자 삽입: 임의의 위치에 문자 하나를 삽입합니다.
2. 문자 삭제: 임의의 위치의 문자 하나를 삭제합니다.
3. 문자 대체: 임의의 위치의 문자 하나를 다른 문자로 바꿉니다.
문자열 $A$를 $B$로 만드는 데 필요한 최소 연산 횟수(최소 편집 거리, Levenshtein Distance)를 구하는 프로그램을 작성하시오.
[제약 조건]
• 테스트 케이스 수 $T$
• 각 문자열의 길이는 $1$ 이상 $2{,}000$ 이하의 알파벳 대문자입니다.
입력 설명
첫째 줄에 테스트 케이스의 개수 $T$가 주어집니다.
각 테스트 케이스마다 두 줄에 걸쳐 문자열 $A$와 $B$가 주어집니다. 각 문자열의 길이는 $1$ 이상 $2000$ 이하이며, 알파벳 대문자로만 구성됩니다.
각 테스트 케이스마다 두 줄에 걸쳐 문자열 $A$와 $B$가 주어집니다. 각 문자열의 길이는 $1$ 이상 $2000$ 이하이며, 알파벳 대문자로만 구성됩니다.
출력 설명
각 테스트 케이스마다 최소 편집 거리를 한 줄에 하나씩 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
1
FOOD
MONEY
출력 예시
COPY
복사되었습니다!
복사되었습니다!
4도움
$dp[i][j]$를 $A$의 접두사 $A[0 \dots i-1]$과 $B$의 접두사 $B[0 \dots j-1]$의 최소 편집 거리라고 합시다. 만약 두 문자가 같으면($A[i-1] == B[j-1]$) $dp[i][j] = dp[i-1][j-1]$ 입니다. 서로 다르면 삽입, 삭제, 대체 중 최소 비용을 택합니다. 즉, $dp[i][j] = \min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1)$ 입니다. 이중 반복문을 통해 $O(|A| \times |B|)$ 시간에 해결할 수 있습니다.