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

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

도훈이가 갖고 있는 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

DNA 조합 timer 1초 memory 128MB

DNA 조합 1초 128MB