Informatica Online Judge

  소 유전학2 [1997 / 07CD]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 12   Total Tried : 13


The Champion of this Problem (C++) : t1234 - 0ms / 498byte
My Best Submission (C++) : N/A

[USACO]

Background

농부 존은 n마리의 얼룩소와 n마리의 검은소를 가지고 있다. 소 유전체학 코스를 공부한 존은 얼룩소의 얼룩들은 소 유전자의 여러 부분에 의해서 돌연변이가 일어났다고 확신했다.

존은 많은 돈을 들여 소들의 유전자 염기 서열을 분석했는데, 유전자 염기 서열의 길이는 m 이고, A, C, G, T 의 4가지의 염기 순서로 기록되어있었다.

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번 위치가 함께 얼룩과 관련된 것이라고 추정했다.

2번째와 4번째 위치의 염기들을 살펴보면, G와 C인 경우에는 얼룩소이고, 검은소에서는 각 위치가 G와 C인 경우가 없기 때문이다. 다른 얼룩소의 2번째와 4번째 염기 조합도 검은소의 염기 조합에서 같은 것이 나타나지 않는다.(염기 서열 조합이 검정소에서의 조합에서 나타나지 않는다면 얼룩을 만들어내는 조합이라고 추정할 수 있다.)

하지만, 존은 1개 또는 2개의 염기 위치만으로는 얼룩과의 연관성을 설명할 수 없다고 생각했고, 3개의 염기 위치 조합으로 가능할 것이라고 생각했다.

소들의 염기서열이 입력될 때, 얼룩과 관련될 것이라고 추정할 수 있는 3개의 염기 위치 조합으로 가능한 경우의 수를 찾아 출력해보자.

Input

첫 번째 줄에는 얼룩소/검은소의 마릿수(n)와 염기서열의 길이(m)가 공백을 두고 입력된다.
(1 <= n <= 500, 3<= m <= 50)
두 번째 줄부터 n줄에 걸쳐 얼룩소의 염기서열이 입력되고,
그 다음 줄부터 n줄에 걸쳐 검은소의 염기서열이 입력된다.

Output

얼룩과 관련된 3개의 위치 염기 세트로 가능한 경우의 가짓수를 출력한다.

IO Example

입력
3 8
AATCCCAT
GATTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT

출력
22

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]