문제
인간의 염기서열이 A, T, G, C 4개로 구성된다는 것을 잘 알려져 있다.
생물학에서는 질병을 진단하고 새로운 약물을 설계하는데 사용할 수 있기 때문에
인간의 유전자를 파악하고 그들의 기능을 결정하는 것에 관심이 많다.
당신은 2개의 유전자가 주어질 때 유전자의 유사도를 구하는 프로그램을 작성해야한다.
예를 들어 2개의 유전가 “AGTAGTG”, “GTTAG”가 주어지면
적당하게 공백(‘-’로 표시)을 삽입하여 길이를 같게 정렬하면, 다음과 같이 된다.
AGTAGT-G
-GT--TAG
이제 다음과 같은 점수 표에 따라 점수를 구한다.
위 유전자의 점수는
(-3)+5+5+(-2)+(-3)+5+(-3)+5=9점이다.
또 다른 정렬방법으로
AGTGATG
-GTTA-G
가 있다.
이 경우는 (-3)+5+5+(-2)+5+(-1)+5=14점으로 점수가 더 높다.
더 높은 점수를 구할 수 있는 정렬이 없기 때문에 이 두 유전자의 점수는 14점이다.
입력
입력은 두 줄로 이루러지는데 각 유전자의 정보가 주어진다.
각 줄의 첫 번째 정수는 유전자의 길이 n(n<=100)이고,
그다음부터 길이만큼 유전자의 정보가 대문자로 공백이 없이 들어온다.
출력
두 유전자의 가장 높은 점수를 출력한다.
예제
7 AGTGATG
5 GTTAG
14
출처
ACM 아시아지역 대전2001 D
로그인해야 코드를 작성할 수 있어요.