골드 IV설명
어떤 워드프로세서의 맞춤법 교정기는 잘못 입력된 단어 \(A\)를 사전에 있는 단어 \(B\)로 바꾸는 데 필요한 최소 편집 횟수를 계산한다. 한 번의 편집으로 할 수 있는 연산은 다음 세 가지이다.
- 한 글자를 삽입한다.
- 한 글자를 삭제한다.
- 한 글자를 다른 글자로 교체한다.
각 연산의 비용은 모두 \(1\)이다. 문자열 \(A\)를 \(B\)로 만들기 위해 필요한 최소 편집 횟수(편집 거리)를 구하여라.
제약
- \(1 \le |A|, |B| \le 2{,}000\)
입력 형식
첫째 줄에 문자열 \(A\)가 주어진다.
둘째 줄에 문자열 \(B\)가 주어진다.
두 문자열은 알파벳 소문자(a–z)로만 이루어진다.
출력 형식
\(A\)를 \(B\)로 바꾸는 최소 편집 횟수를 한 줄에 출력한다.
예제 1
입력
sunday
saturday
출력
3설명
sunday → saturday는 최소 \(3\)번의 편집이 필요하다.
예제 2
입력
apple
apple
출력
0설명
두 단어가 같으므로 편집이 필요 없어 \(0\).
문제 정보
riseoj 작성
출처 Original
태그