최소 편집

두 문자열 $A$와 $B$가 주어졌을 때, $A$에 연산을 최소 횟수로 적용해 $B$로 만드는 문제를 최소 편집 문제라고 한다.

$A$에 적용할 수 있는 연산은 다음 3가지다.

1. 삽입: $A$의 한 위치에 문자 하나를 넣는다.
2. 삭제: $A$의 문자 하나를 지운다.
3. 교체: $A$의 문자 하나를 다른 문자로 바꾼다.

두 문자열이 주어졌을 때 최소 편집 횟수를 구하는 프로그램을 작성하시오.

첫째 줄에 문자열 $A$, 둘째 줄에 문자열 $B$가 주어진다. 두 문자열은 알파벳 소문자로만 이루어지며, 길이는 각각 1000글자를 넘지 않는다.

첫째 줄에 $A$를 $B$로 만드는 최소 편집 횟수를 출력한다.