농부 존은 N마리의 얼룩이 있는 소들과 N마리의 얼룩이 없는 소들을 기르고 있습니다. 그는 방금 소의 유전자에 관한 과정을 마친 후, 자신의 소들의 얼룩이 유전자 변이에 의해 발생한다고 확신합니다.

농부 존은 큰 비용을 들여 자신의 소들의 유전자를 시퀀싱합니다. 각 유전자는 A, C, G, T의 네 문자를 사용하여 길이 M의 문자열로 구성됩니다. 그가 소들의 유전자 정보를 나열하면 다음과 같은 표를 얻게 됩니다 (여기서는 N=3을 예시로 듭니다):

위치:      1 2 3 4 5 6 7 ... M
얼룩 있는 소 1: A A T C C C A ... T
얼룩 있는 소 2: G A T T G C A ... A
얼룩 있는 소 3: G G T C G C A ... A

얼룩 없는 소 1:  A C T C C C A ... G
얼룩 없는 소 2:  A G T T G C A ... T
얼룩 없는 소 3:  A G T T C C A ... T

농부 존은 표를 살펴보며 2번과 4번 위치가 얼룩을 구분하는 데 충분하다고 추측합니다. 즉, 이 두 위치의 문자를 보면 소가 얼룩이 있는지 없는지를 예측할 수 있습니다 (예를 들어, G와 C가 보이면 그 소는 얼룩이 있다고 예측할 수 있습니다).

농부 존은 유전자의 한두 위치뿐만 아니라 세 개의 다른 위치를 보면 얼룩을 설명할 수 있다고 확신합니다. 이제, 세 개의 서로 다른 위치들이 얼룩을 설명할 수 있는 경우의 수를 구하는 문제입니다.

#4028 upload 2 done 1 how_to_reg 1

Bovine Genomics timer 2s memory 512MB

#4028

Bovine Genomics 2s 512MB