[PCCP 모의고사 #1] 3번 - 유전법칙

문제 설명

멘델은 완두콩을 이용하여 7년간 실험한 결과, 다음과 같은 특별한 법칙을 발견하였습니다.

1. 둥근 완두 순종(RR)을 자가 수분, 즉 같은 유전자끼리 교배할 경우, 다음 세대에 둥근 완두 순종 형질만 나타난다.
2. 주름진 완두 순종(rr)을 자가 수분할 경우, 다음 세대에 주름진 완두 순종 형질만 나타난다.
3. 두 순종을 교배한 잡종(Rr)을 자가 수분할 경우, 다음 세대의 형질은 RR:Rr:rr=1:2:1의 비율로 나타난다. (아래 그림 참조)

멘델의 법칙을 공부한 진송이는, 직접 완두콩의 자가 수분 실험을 진행했습니다. 진송이의 실험에서 완두콩 한 개를 자가 수분한 결과는 다음과 같습니다.

1. 각 완두콩은 자가 수분해서 정확히 4개의 완두콩 후손을 남긴다.
2. 잡종 완두콩(Rr)은 자가 수분해서 첫째는 RR, 둘째와 셋째는 Rr, 넷째는 rr 형질의 후손을 남긴다.
3. 순종 완두콩(RR, rr)은 자가 수분해서 자신과 같은 형질의 후손을 남긴다.

잡종 완두콩(Rr) 1대부터 시작한 가계도로 그려보면 그림 2와 같습니다.

진송이는 이러한 완두콩의 자가 수분 실험 결과를 정리하고 싶어합니다. 하지만, 세대를 거듭할수록, 완두콩의 수가 너무 많아져 모든 가계도를 기록하기 어려워졌습니다. 진송이는 가계도를 전부 기록하는 것 대신, 완두콩의 세대와 해당 세대에서 몇 번째 개체인지를 알면 형질을 바로 계산하는 프로그램을 만들려 합니다.

각 세대에서 맨 왼쪽 개체부터 첫 번째, 두 번째, 세 번째, ...개체로 나타냅니다. 예를 들어 그림 2에서 2세대의 네 번째 개체의 형질은 "rr"이며, 3세대의 9번째 개체의 형질은 "RR"입니다.

형질을 알고 싶은 완두콩의 세대를 나타내는 정수 n과, 해당 완두콩이 세대 내에서 몇 번째 개체인지를 나타내는 정수 p가 2차원 정수 배열 queries의 원소로 주어집니다. queries에 담긴 순서대로 n세대의 p 번째 개체의 형질을 문자열 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 1 ≤ queries의 길이(쿼리의 개수) ≤ 5
• queries의 원소는 [n, p] 형태입니다.
  • 1 ≤ n ≤ 16
  • 1 ≤ p ≤ 4n-1

 

먼저 문제에 주어진 그림의 3rd generation의 각 완두콩에 아래와 같이 번호를 붙여보겠습니다.

문제 지문에서는 첫 번째, 두 번째...와 같이 시작하지만 여기서는 0번부터 번호를 붙였습니다. 그 아래에는 번호를 4로 나눈 나머지를 표기해 두었습니다. 이를 잘 살펴보면, 번호를 4로 나눈 나머지가 부모 완두콩의 몇 번째 개체인지 나타낸다는 점을 알 수 있습니다. 정리하면 다음과 같습니다.

• n세대의 p번 개체는 n - 1번 세대의 p % 4번째 자손입니다.

또, 그림을 잘 살펴보면 p를 4로 나눈 몫이 부모 세대의 번호라는 사실도 알 수 있습니다. 예를 들어 3세대의 2번을 4로 나눈 몫은 0이고, 이는 2세대의 첫 번째 개체의 번호가 0번임을 나타냅니다. 마찬가지로, 3세대의 14번을 4로 나눈 몫은 3이고, 이는 2세대의 마지막 개체의 번호를 나타냅니다. 바꿔 말하면 3세대의 5번 개체의 자손의 번호는 20 ~ 23번이 된다는 뜻이기도 합니다. 정리하면 다음과 같습니다.

• n세대의 p번개체의 부모의 번호는 p를 4로 나눈 몫과 같습니다.

이과 같은 사실을 이용하여 재귀적으로 부모 세대의 형질을 알아낸 후, 자신이 몇 번째 자손인지를 구해 나간다면 원하는 개체의 형질을 알아낼 수 있습니다.

---

코드 작성 :

현재 자신의 세대와 번호를 이용해 부모 세대의 형질을 재귀적으로 계산합니다. 1세대의 형질은 "Rr"이므로, 1세대에 도달했다면 함수를 더 호출하지 않고 바로 형질을 return 해줍니다. 구해온 부모 세대의 형질에 따라 자신의 형질을 적절히 계산해서 return 합니다. 부모 세대의 번호를 구하기 위해 몫을 계산하는 부분과 자신이 몇 번째 자손인지 구하기 위해 나머지를 구하는 부분을 잘 살펴보세요.

class Solution {
    // 잡종 완두콩(Rr)을 자가 수분한 결과를 child 배열에 저장합니다.
    public String[] child = {"RR", "Rr", "Rr", "rr"};

    // gen세대의 x번째 개체의 형질을 return 할 재귀 함수입니다.
    public String back(int gen, int x){
        if (gen == 1) // 1세대 형질은 잡종 완두콩(Rr)입니다.
            return "Rr";

        // 부모의 형질을 parent에 저장합니다.
        // 부모의 번호는 x를 4로 나눈 몫입니다.
        String parent = back(gen - 1, x / 4);

        // 부모의 형질에 따라 현재 개체의 형질을 return합니다.
        if (parent == "Rr")  // 부모가 잡종일 경우
            return child[x % 4];  // x % 4는 몇 번째 자식인지를 의미합니다.
        else  // 부모가 순종일 경우
            return parent;  // 부모와 자식의 형질이 같습니다.
    }
    public String[] solution(int[][] queries) {
        String[] answer = new String[queries.length];
        for(int i = 0; i < queries.length; i++){
            int n = queries[i][0];
            int p = queries[i][1];
            // n세대의 p번째 개체의 형질을 가져옵니다.
            // 0번부터 시작하기 위해 p에서 1을 빼줍니다.
            answer[i] = back(n, p - 1);
        }
        return answer;
    }
}