유전자 timer 1초 memory 256MB

최근에 인간의 유전자 염기서열을 밝히는 인간게놈(genome) 프로젝트가 완료되었다. 

염색체내의 유 전자의 염기서열을 알아내는 방법은 다음과 같다. 

한 염색체의 염기서열이 너무 길면 현재의 기술로는 그 내용을 알아낼 수 없다.

따라서, 이를 PCR이라는 방식을 이용하여 여러 벌로 복제한 다음, 효소를 가하게 되면 염색체 조각들로 나뉘어진다. 

이 염색체 조각들은 길이가 충분히 짧으므로 현재의 기술로 그 내용을 밝혀 낼 수 있다. 

내용이 밝혀진 염색체 조각들을 다시 이어서 여러 벌의 동일한 염색체로 복구하여, 

원래 염색체의 염기서열을 알아낸다. (유전자의 염기는 A, G, T, C라는 네 종류가 있으며, 이 들의 조합으로 염기서열을 표시한다.)

예를 들어, 염색체의 염기서열이 있을 때, 이 염기서열을 3벌로 복제한 뒤, 

효소를 가하여 11개로 나 누고, 그 조각들의 내용을 밝힌 결과가 다음과 같다고 하자.

CGATGCCA CAGGAAGCG AGGTGCCC CAGGA AGGTGCCCGATGC GGAAGCGATGGAGCTTT ATGGAGCTTT GATGC CCGTGGA AGCGATGG TTTCGA

이 조각들을 다시 모아서 동일한 3벌의 염기서열로 재구성하면 다음과 같이 되고, 

이를 통해서 전체 염색체의 염기서열을 알아낼 수 있다. 조각들은 그대로 사용할 수도 있고, 

뒤집어서 사용할 수도 있다. 

예를 들어 위의 마지막 조각인 TTTCGA는 AGCTTT로 뒤집어서 아래의 마지막 염기서열을 만드는데 사용하였다.

AGGTGCCCGATGC CAGGAAGCG ATGGAGCTTT AGGTGCC CGATGCCA GGAAGCGATGGAGCTTT AGGTGCCC GATGC CAGGA AGCGATGG AGCTTT

복제된 염색체의 벌 수와 내용이 밝혀진 염색체 조각들이 입력으로 주어져 있을 때 전체 염기서열을 구하는 프로그램을 작성하시오.