문제
A, T, G, C 네 종류의 문자만으로 이루어진 길이 N인 문자열 a와 길이 M인 문자열 b가 주어진다. a를 b로 바꾸고 싶은데, 사용 가능한 연산은 아래의 세 가지 뿐이다.
(1) 삭제 : a의 문자 중 하나를 삭제한다.
(2) 삽입 : a의 가운데에 아무 문자나 삽입한다.
(3) 치환 : a의 문자 중 하나를 다른 문자로 바꾼다.
물론 연산의 횟수를 최소화해야 한다.
a=AGTCTGACGC이고, b=AGTAAGTAGGC 일 때, 아래의 그림을 보자.
위의 그림은 4번의 치환과 1번의 삽입을 사용해서 총 5번의 연산을 했다.
하지만 아래 그림과 같이 하면 3번의 치환과 1번의 삽입만 가지고도 a를 b로 만들 수 있다.
이번에는 a=AGTAAGTAGGC 이고 b=AGTCTGACGC 인 경우를보자.
3번의 치환과 1번의 삭제만으로 a를 b로 만들 수 있다.
a와 b가 주어지면 변환을 완료하기 위해 필요한 최소 연산 횟수를 구하자.
입력
첫 번째 줄에는 a의 길이 N( 1<= N <= 1000)과 문자열 a가 공백으로 구분되어 입력된다.
두 번째 줄에는 b의 길이 M( 1<= M <= 1000)과 문자열 b가 공백으로 구분되어 입력된다.
출력
최소 연산 횟수를 출력한다.
예제1
입력
10AGTCTGACGC
11AGTAAGTAGGC
출력
4