2326번 - 최소 편집 문제 2

문제

최소 편집 문제는 두 개의 문자열이 주어졌을 때 “삽입(insert)”, “삭제(delete)”, “대체(replace)”의 연산으로 하나의 문자열을 다른 하나의 문자열과 같게 만드는데 사용되는 최소 편집 회수를 구하는 문제이다. 하지만 이렇게 익히 알려진 문제를 또 다시 낼 리가 있겠는가? 그래서 문제에 새로운 편집기술이 하나가 추가되었는데 기존의 편집기술도 포함해서 다시 문제를 정리 해보도록 하자.

예를 들면 X = aabcc, Y = abcca와 같이 두 개의 문자열 X, Y가 주어진다. 이때 문자열 X에 다음의 편집기술을 최소로 사용해서 문자열 X가 문자열 Y와 같아지도록 만들어야 한다.

1. 삽입: 문자열 X의 어느 위치에라도 원하는 글자 하나를 삽입 할 수 있다.
2. 삭제: 문자열 X의 어느 글자라도 원하는 한 글자를 삭제 할 수 있다.
3. 대체: 문자열 X의 어느 글자라도 원하는 한 글자로 대체 할 수 있다.
4. 교환: 문자열 X의 어느 두 인접한 글자라도 그 위치를 서로 바꿀 수 있다.

문자열 X, Y가 주어지면 위의 네 가지 편집기술을 사용하여 두 개의 문자열을 같게 만드는 최소 편집 회수를 구하시오.

입력

첫 번째 줄에 문자열 X가 주어지고 두 번째 줄에 문자열 Y가 주어진다. 각 문자열의 길이는 1,000 이하이고, 알파벳 소문자로만 이루어져 있다.

출력

최소 편집 회수를 출력한다.

제한

힌트