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가 주어지면 변환을 완료하기 위해 필요한 최소 연산 횟수를 구하자.

최소 편집 timer 1000초 memory 64MB

최소 편집 1000초 64MB