최소 편집 2
면접 대비시간 제한2초메모리 제한512 MB
두 문자열 A와 B가 주어질 때 삽입, 삭제, 교체, 인접 교환 연산만으로 A를 B로 바꾸는 최소 연산 횟수를 구한다. 두 문자열의 길이는 최대 1000이다.
문제
두 문자열 A와 B가 주어졌을 때, A에 연산을 최소 횟수로 적용해 B로 만드는 문제를 최소 편집 문제라고 한다.
A에 적용할 수 있는 연산은 네 가지다.
- 삽입: A의 한 위치에 문자 하나를 넣는다.
- 삭제: A에서 문자 하나를 지운다.
- 교체: A의 문자 하나를 다른 문자로 바꾼다.
- 교환: A에서 인접한 두 문자의 자리를 맞바꾼다.
연산은 현재 문자열에 차례대로 적용한다.
두 문자열이 주어지면 최소 편집 횟수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 문자열 A가, 둘째 줄에 문자열 B가 주어진다. 두 문자열은 알파벳 소문자로만 이루어지고, 길이는 1자 이상 1000자 이하이다.
출력
첫째 줄에 최소 편집 횟수를 출력한다.