DNA 조합 > 문제은행



실력키우기 재귀호출

2217 : DNA 조합

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 16 회    시도횟수: 57 회   



철기는 학교에서 배운 유전자 실험을 이용해서 자신만의 실험을 계획하고 있다

(프로그램 짜주는 복제인간을 만드는 것이 목표라고 한다).

철기가 갖고 있는 DNA 조각은 n(2<=n<=7)개가 있다. 

이들 DNA 조각은 복제인간이 가져야 할 중요한 유전자를 담고 있기 때문에,

이 조각들의 정보를 그대로 유지시키면서 가장 짧은 DNA 순열을 새로 만들고 싶다.

DNA 순열을 조합하는 과정은 아래와 같다.

1) n개의 DNA조각을 임의의 순서로 나열한다.
2) 인접한 두 DNA조각에서 앞쪽 조각의 오른쪽 끝 부분이
   뒤쪽 조각의 왼쪽 끝 부분과 최대한 많이 일치하는 부분을 찾는다.
3) 모든 인접한 두 DNA에서 중복되는 부분을 제거하고 나머지 부분을
   순서대로 모아 새로운 문자열을 만든다.

 

예를 들어, ‘GATTA’와 ‘TACA’는 ‘GATTACA’로 조합될 수 있다. 

왜냐하면 ‘GATTA’의 오른쪽 두 글자 ‘TA’가 ‘TACA’의 왼쪽 두 글자 ‘TA’와 일치하기 때문이다. 

어떤 경우에는 한 조각이 다른 조각의 내용을 모두 포함하고 있을 수도 있고, 어떤 경우에는 단 한 글자도 일치하지 않을 수도 있다.

‘GATTACA’와 ‘TTACA’는 완벽하게 겹치는 반면에 ‘GATTACA’와 ‘TTA’는 한 글자도 겹치지 않는다. 

 

아래에 조합의 몇 가지 예가 있다.

GATTA+TACA -> GATTACA
TACA+GATTA -> TACAGATTA
TACA+ACA -> TACA
TAC+TACA -> TACA
ATAC+TACA -> ATACA
TACA+ACAT -> TACAT

 

 




첫 줄에 n이 입력되고, 두 번째 줄부터 n개의 줄에 걸쳐 각 DNA 조각이 입력된다.

DNA조각의 길이는 1 ~ 7 이다.



첫 번째 줄에 n개의 DNA를 모두 조합해서 하나의 DNA 순열로 만들었을 때 최소 길이를 출력한다.



4
GATTA
TAGG
ATCGA
CGCAT
13


3
ABC
BCD
ABCD
4



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