시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 76 7 6 12.000%

문제

최소 편집 문제는 두 개의 문자열이 주어졌을 때 “삽입(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 이하이다.

출력

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

예제 입력

abcdefg
abdecgcabf

예제 출력

6

힌트