정올이는 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 C T C G C A ... T

일반말 3: A C T T C C A ... T

이 표를 자세히 살펴본 정올이는 2번째 위치가 얼룩을 설명할 수 있는 잠재적인 위치라고 추측한다. 즉, 이 위치에서 나타나는 문자만 보고도 어떤 말이 얼룩이 있는지 없는지를 구별할 수 있다는 것이다. 예를 들어, 2번째 위치에서 A나 G는 얼룩말을 의미하고, C는 일반말을 의미한다. T는 이 위치에서는 나타나지 않으므로 무시할 수 있다. 첫 번째 위치는 자체적으로 얼룩을 설명할 수 없다. 왜냐하면 첫 번째 위치에서 A는 얼룩말일 수도, 일반말일 수도 있기 때문이다.

정올이는 말들의 유전체를 보고, 얼룩을 설명할 수 있는 위치가 몇 개인지 세고자 한다.

#4031 upload 2 done 2 how_to_reg 2

얼룩말 유전자 timer 1s memory 128MB

#4031

얼룩말 유전자 1s 128MB