유사도 구하기

프로그램 명: similarity(special judge)

제한시간: 1 초

인간의 유전자가 4 개의 뉴클레오티드(A,C,G,T)로 구성된 문자열의 형태로 표시된다. 생물학자들은 질병을 고치고 , 새로운 약을 만드는데 도움을 주기 때문에 , 인간의 유전자의 기능을 알아내려는데 많은 관심이 있다.

두 개의 유전자 문자열이 주어 졌을 때, 아래 설명된 규칙에 맞게 유사도를 구하는 것이다.

유사도를 구하는 방법은 두 개의 문자열에 적당히 공백을 추가하여 , 두 개의 문자열의 길이가 같게 만든다음 , 같은 위치에 놓인 뉴클레어티드를 비교하는 방법이다.

예를들어 , AGTGATG 와 GTTAG 의 유사도를 분석해보자. AGTGATG 에 1 개의 공백을 집어넣고 , GTTAG 에 3 개의 공백을 집어 넣어보자. 공백은 - 로 표시한다.

AGTGATG -> AGTGAT-G 
GTTAG   -> -GT--TAG

이렇게 되었을 경우 , 아래 표에서 각 자리에 해당하는 뉴클레오티드 두 개의 점수의 총합을 구하면 된다.(공백 두 개가 같은 위치에 있어서는 안 된다)

A C G T -

A 5 -1 -2 -1 -3

C -1 5 -3 -2 -4

G -2 -3 5 -2 -2

T -1 -2 -2 5 -1

- -3 -4 -2 -1 *

점수를 계산해 보면

(-3)+5+5+(-2)+(-3)+5+(-3)+5=9

가 된다. 공백을 집어넣은 여러 가지 방법 중에서 점수가 최대로 될 때의 값을 유사도라 한다.

AGTGATG 와 GTTAG 의 유사도는

AGTGATG
-GTTA-G

일 때 14 가 된다.

입력은 두 개의 줄로 구성되어 있다. 각 줄에는 유전자 정보가 들어있는 한 개의 정수(T) 와 한 개의 문자열(S) 이 있다. T( 1 <= T <= 100)는 S 의 길이를 나타낸다.

첫 줄에 유사도의 최대 값을 출력한다. 다음 두 줄은 유사도가 최대값인 경우의 방법을 출력한다.

입력

7 AGTGATG
5 GTTAG

출력

14
AGTGATG
-GTTA-G

출처: Taejon 2001
special judge:pl0892029