최소 편집 > 문제은행

본문 바로가기


알고리즘 다이나믹1

2191 : 최소 편집

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 575 회    시도횟수: 1554 회   



A, T, G, C 네 종류의 문자만으로 이루어진 길이 N인 문자열 a와 길이 M인 문자열 b가 주어진다. a를 b로 바꾸고 싶은데, 사용 가능한 연산은 아래의 세 가지 뿐이다.

(1) 삭제 : a의 문자 중 하나를 삭제한다.
(2) 삽입 : a의 가운데에 아무 문자나 삽입한다.
(3) 치환 : a의 문자 중 하나를 다른 문자로 바꾼다.

물론 연산의 횟수를 최소화해야 한다.
a=AGTCTGACGC이고, b=AGTAAGTAGGC 일 때, 아래의 그림을 보자.

 

 

75aaf69980fa1f33c5b54a688ed39a00_1450939 

 
위의 그림은 4번의 치환과 1번의 삽입을 사용해서 총 5번의 연산을 했다.
하지만 아래 그림과 같이 하면 3번의 치환과 1번의 삽입만 가지고도 a를 b로 만들 수 있다.

 

 

75aaf69980fa1f33c5b54a688ed39a00_1450939 

 

이번에는 a=AGTAAGTAGGC 이고 b=AGTCTGACGC 인 경우를보자.

 

 

75aaf69980fa1f33c5b54a688ed39a00_1450939 

 

3번의 치환과 1번의 삭제만으로 a를 b로 만들 수 있다.

a와 b가 주어지면 변환을 완료하기 위해 필요한 최소 연산 횟수를 구하자.


첫 번째 줄에는 a의 길이 N( 1<= N <= 1000)과 문자열 a가 공백으로 구분되어 입력된다.두 번째 줄에는 b의 길이 M( 1<= M <= 1000)과 문자열 b가 공백으로 구분되어 입력된다.



최소 연산 횟수를 출력한다.


[Copy]
10 AGTCTGACGC
11 AGTAAGTAGGC
[Copy]
4



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.