DNA 조합 > 문제은행 : 정보올림피아드&알고리즘



2217 : DNA 조합

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
160 회   
시도횟수
407 회   

문제

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

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

도훈이가 갖고 있는 DNA 조각은 n(2<=n<=7)개가 있다. 

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

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

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

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

4) 새로운 문자열을 만들때 인접한 문자열의 공통부분만 제거할 수 있음에 유의한다.

   예를 들어 ABC, D, BCD 를 순서대로 연결하는 경우 ABCD가 아닌 ABCDBCD가 된다. 

   

예를 들어, ‘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

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

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

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP