4551 - 돌연변이 (Challenge)

• Submit
• Status
• Discuss
• Summary

Description

염기서열을 복제하는 중에 발생하는 유전적 변이에는 치환,삽입, 결실,중복, 역위 5가지 종류가 있다.

치환: 염기 하나가 다른 염기로 바뀐 것 (ATGC -> ACGC)

삽입: 염기 하나가 더 추가된 것 (ATGC -> ATCGC)

결실: 염기서열을 복제하다가 중간에 건너뛴 것 (ATGC -> AC)

중복: 염기서열이 중간에 한번 더 복제되는 것 (ATGC -> ATGTGC)

역위: 염기서열이 중간에 반대로 붙는 것 (ATGC -> AGTC)

정상적인 염기서열을 변이시켜 원하는 염기서열로 만들기 위해서는 최소 몇 개의 변이를 거쳐야 하는지 구해보자.

Input

* Line 1: 정상적인 염기서열 (길이: 1 이상 9 이하)

* Line 2: 만들려는 염기서열  (길이: 1 이상 9 이하)

 

Output

* Line 1: 원하는 염기서열로 만들기 위해 거쳐야하는 최소 변이 횟수

Sample Input

AAACTG
AAACAGATC

Sample Output

3

Hint

AAACTG

AAACACTG (복제)

AAACAGTC (역위)

AAACAGATC (삽입)

총 3번의 변이만 거치면 된다.