USACO 2017 US Open Bronze 2. Bovine Genomics- 유전자 분석 > 문제은행 : 정보올림피아드&알고리즘




3067 : 유전자 분석

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
66 회   
시도횟수
153 회   

문제

백구(흰색 강아지)만을 키우던 정현이네 집에 어느 날 새로운 강아지 식구가 태어났다. 

여러 마리가 태어났는데 그중 몇 마리가 바둑강아지(흰색과 반점이 있는 강아지)였다. 

어떻게 바둑이가 태어났을까 고민하던 정현이는 유전자 검사를 의뢰하였다. 

유전자 변이가 이유일 것이라고 생각했기 때문이다. 

바둑이와 백구의 유전자는 한 종류의 유전자에서만 차이가 난다는 정보도 얻었다. 

유전자 정보를 이용하여 바둑이의 반점을 일으키는 유전자가 몇 번째 유전자인지 찾으려고 한다.
이러한 가능성이 있는 유전자는 모두 몇 가지나 있을까?
정현이를 도와 바둑이의 반점을 일으키는 유전자를 찾아보자.

 

예를 들어 백구 3마리와 바둑이 3마리의 유전자 검사결과가 아래와 같이 나왔다고 가정하자. 

두 부류의 강아지 유전자 검사결과에서 2번 유전자의 검사결과를 비교해 보면 백구 강아지들과 바둑강아지들 사이에 공통적인 유전자가 존재하지 않는다. 

따라서 우리는 2번 유전자 자리에 C라는 유전자가 바둑무늬를 만드는 유전자일 가능성이 있다고 유추할 수 있다. 

 

 


입력형식

첫 행에 각 강아지 종류 당 마리 수 N과 유전자의 길이 M이 주어진다. ( 1 <= N, M <= 100) 다음 행부터 N행 M열에 백구 N마리의 유전자 정보가 주어진다. 다음 행부터 N행 M열에 바둑이 N마리의 유전자 정보가 주어진다. 유전자 정보는 ‘A’, ‘C’, ‘G’, ‘T’ 로만 이루어진다.

출력형식

바둑무늬를 일으킬 가능성이 있는 유전자는 모두 몇 종류인지 출력한다.

입력 예

3 8
AATCCCAT
GATTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT

출력 예

1


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP