KOI 본선 2004 중5- DNA유사도 > 문제은행 : 정보올림피아드&알고리즘




1858 : DNA유사도

제한시간
1000 ms   
메모리제한
256 MB   
해결횟수
155 회   
시도횟수
726 회   

문제

모든 생물의 DNA 서열은 A, C, G, T 네 개의 문자로 표현된다.

 

두 DNA 서열이 얼마나 비슷한가를 알아내기 위하여 유사도를 측정한다. 

두DNA 서열의 유사도를 측정하기 위해서 먼저 각 서열의 임의의 위치에 공백을 넣어 길이를 같게 만든다.

 

이렇게 길이가 같아진 두 서열 간의 점수는 다음과 같이 계산된다.

 

1. 같은 위치에 공백이 아닌 같은 문자가 있으면 3을 더한다.

2. 같은 위치에 서로 다른 문자가 있거나 둘 중 하나의 위치에 공백이 있으면 2를 뺀다.

 

두 DNA 서열의 유사도는 각 DNA 서열의 임의의 위치에 공백을 넣어 위의 방법대로 얻을 수 있는 최대 점수이다. 

예를 들어 AGTCAG와 ATGTG라는 두 DNA서열의 경우 , 

<그림 1>과 같이 공백을 넣으면 점수가 3이 되고, <그림 2>와 같이 공백을 넣으면 점수는 6이 된다.

 

  

 

AGTCAG와 ATGTG의 경우 임의의 위치에 공백을 넣어 얻을 수 있는 최대 점수는 6이므로 AGTCAG와 ATGTG의 유사도는 6이 된다.

 

DNA 서열의 부분 서열은 DNA 서열 중 연속한 일부분을 추출하여 얻을 수 있는 서열을 말한다.

예를 들어 AGTCAG라는 서열에서 첫 번째 문자부터 세 번째 문자까지를 추출하면 AGT라는 부분 서열을 얻을 수 있고,

두 번째 문자부터 다섯 번째 문자까지 추출하면 GTCA라는 부분 서열을 얻을 수 있다.

 

두 DNA 서열에서 같은 정보를 담고 있는 부분을 찾아내는 방법 중에 하나는 두 DNA의 부분 서열 쌍 중 유사도가 가장 큰것을 찾아내는 것이다.

 

예를 들어 두 DNA 서열 AGTCAG 와 ATGTG의 경우 AGTCAG에서 부분 서열 AGT를 얻고, 

ATGTG에서 부분 서열 ATGT를 얻으면 이 둘의 유사도는 아래와 같이 7이 된다.

 


 

두 DNA 서열을 입력받아 이들 DNA의 부분 서열 쌍 중 유사도가 가장 큰것을 찾아 그 유사도와 부분 서열 쌍을 출력하는 프로그램을 작성하시오.

 


입력형식

입력 파일의 첫째 줄에는 첫 번째 DNA의 서열의 길이가 추어지고 둘째 줄에는 첫 번째 DNA서열이 주어진다.

셋째 줄에는 두 번째 DNA의 서열의 길이가 주어지고 넷째 줄에는 두 번째 DNA 서열이 주어진다. 

DNA 서열의 길이는 1000이하이며, DNA 서열을 나타내는 문자들 사이에는 공백이 없다. 

첫 번째 DNA와 두 번째 DNA는 적어도 하나 이상 공통 문자를 갖는다.


출력형식

첫째 줄에는 두 DNA 서열의 부분 서열 쌍 중 유사도가 가장 큰 것의 유사도를 출력한다.

둘째 줄과 셋째 줄에는 유사도가 가장 큰 부분 서열의 쌍을 출력하는데, 

둘째 줄에는 첫 번째 DNA 서열에서 추출한 부분 서열을 출력하고,

셋째 줄에는 두 번째 DNA 서열에서 추출한 부분 서열을 출력한다. 

만약 두 DNA 서열의 부분 서열 쌍 중 유사도가 가장 큰 쌍이 둘 이상일 경우 하나만 출력하면 된다.


입력 예

6
AGTCAG
5
ATGTG

출력 예

7
AGT
ATGT


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP