파일 업로드

반점 유전자 분석

profile
실행 시간 제한메모리 제한
2 초512 MB
📃 해결할 문제

유전학자 세현은 NN마리의 반점이 있는 소와 NN마리의 반점이 없는 소를 소유하고 있다. 소 유전학 박사 과정을 밟은 그는, 소의 반점이 소 유전체의 한 위치에서 발생하는 돌연변이때문이라고 확신합니다.

큰 비용을 들여, 세현은 소들의 유전자를 분석한다. 각 유전자는 A, C, G, T의 네 개의 문자로 구성된 길이 MM의 문자열이다. 그가 소들의 유전자를 맞춰보면, 아래와 같은 표를 얻게 된다. 이는 N=3N=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가 점박이를 설명할 수 있는 유전체의 잠재적 위치라는 것을 추측할 수 있다. 즉, 이 위치의 문자만을 살펴보면, 세현은 어떤 소가 반점이 있는 소이고 어떤 소가 아닌지를 예측할 수 있다(여기서, A 또는 G는 반점이 있는 소를, C는 반점이 없는 소를 의미한다; T는 세현의 소 중에서 위치 2에서 나타나지 않으므로 관련이 없다). 위치 1은 반점이 있는 소를 설명하는 데에 자체로는 충분하지 않다. 이 위치의 A는 반점이 있는 소 또는 반점이 없는 소를 나타낼 수 있기 때문이다.

세현의 소들의 유전자가 주어진다면, 반점이 있는 소일 가능성을 설명할 수 있는 위치의 수를 세어 보세요.

💻 입력

첫 번째 입력 줄에는 NNMM이 있고, 이들은 최대 100의 크기를 가진 양의 정수다. 다음 NN줄에는 각각 길이 MM의 문자열이 포함되어 있으며, 이들은 점박이 소들의 유전자를 설명한다. 마지막 NN줄은 반점이 없는 소들의 유전자를 설명한다.

🖨️ 출력

유전자에서 반점이 있는 소를 설명할 수 있는 위치 수(범위는 0M0 \ldots M의 정수)를 세어주세요. 위치는 만약 반점 특성이 세현의 소의 집단에서 완벽한 정확성으로 예측 될 수 있다면, 이 위치는 반점이 있는 소를 설명할 수 있는 잠재적인 위치입니다.


💻 예제 입력 1
3 8
AATCCCAT
GATTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT
🖨️ 예제 출력 1
1

출처: USACO 2017 US Open Contest, Bronze Problem 2. Bovine Genomics