The Turn of the Shrew

몽고메리 모로 박사는 여러 해 동안 야생에 사는 북부 마다가스카르 얼룩 뒤쥐 개체군을 관찰해 왔다. 그는 이 지역의 모든 뒤쥐를 꼼꼼히 조사하여 각각의 두드러진 신체적 특징을 기록하고 이름을 붙였다.

그는 중요한 신체적 특징(예: 갈색 털, 붉은 눈, 흰 발, 두드러진 앞니 등)의 목록을 관리하며, 각 특징이 우성인지 여부를 기록한다. 어떤 특징이 우성이면, 부모 중 한쪽이라도 그 특징을 가지고 있을 경우 자식도 그 특징을 가진다.

최근 그는 이 개체군에서 유전적 돌연변이가 높은 비율로 일어나고 있다고 의심하게 되었다(공동 굴 근처에 있는 이상하게 빛나는 돌 때문일지도 모른다). 지난겨울이 끝나 뒤쥐들이 굴에서 나왔을 때, 그는 어떤 부모 쌍으로도 설명할 수 없는 특징을 가진 어린 개체가 여럿 있음을 발견했다.

각 어린 뒤쥐에 대해, 그 부모 관계를 설명할 수 있는 최소 돌연변이 횟수를 구하는 프로그램을 작성하여라.

입력은 하나 이상의 데이터 집합으로 이루어진다.

각 데이터 집합은 한 마리의 동물을 나타내는 여러 줄로 구성된다. 각 줄은 문자 M, F, C 중 하나로 시작하며, 각각 수컷 성체, 암컷 성체, 자식을 뜻한다. 한 데이터 집합에는 세 종류의 줄이 각각 최소 한 개씩 존재한다. 첫 문자 다음에는 공백 한 칸이 오고, 그 뒤에 0과 1로 이루어진 길이 1 이상 40 이하의 유전 코드가 온다. 한 데이터 집합 안의 모든 유전 코드의 길이는 같다.

유전 코드에서 1은 해당 우성 유전자가 지배하는 신체적 특징을 그 동물이 가지고 있음을, 0은 가지고 있지 않음을 뜻한다. 데이터 집합은 첫 문자가 X인 줄로 끝난다. 모든 입력의 끝은 그 뒤에 연속으로 오는, 첫 문자가 X인 두 번째 줄로 표시된다.

돌연변이가 없다면, 자식은 어떤 위치에서 부모 중 적어도 한쪽이 1을 가질 때에만 그 위치에 1을 가질 수 있고, 두 부모가 모두 그 위치에 0을 가질 때에만 그 위치에 0을 가질 수 있다. (즉, 돌연변이가 없다면 자식의 코드는 두 부모 코드의 비트 OR와 같다.) 부모 쌍은 항상 수컷 성체 한 마리와 암컷 성체 한 마리로 이루어진다. 각 돌연변이는 코드의 위치 한 개만을 바꾼다.

각 자식에 대해, 자식이 입력에 나타난 순서대로 다음 형식의 줄을 한 줄씩 출력한다.

Child K has a minimum of N mutations.

여기서 K는 자식의 번호로 1부터 시작하며 출력하는 줄마다 1씩 증가한다. N은 이 자식이 어떤 부모 쌍에게서 태어났다고 설명할 수 있는 최소 돌연변이 횟수이다.