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

유전 법칙 문제 링크

정답 코드

class Solution {
    public String[] solution(int[][] queries) {
        String[] result = new String[queries.length];
        for(int i = 0; i < queries.length; i++)
            result[i] = queries[i][0] == 1 ? "Rr" : recursive(queries[i][0], queries[i][1]);
        return result;
    }
    private String recursive(int n, int p) {
        int cnt = (int) Math.pow(4, n - 1);
        if(p <= cnt / 4) return "RR";
        if(p > cnt / 4 * 3) return "rr";
        if(n == 2) return "Rr";
        if(p > cnt / 4 && p <= cnt / 2) return recursive(n - 1, p - cnt / 4);
        return recursive(n - 1, p - cnt / 2);
    }
}

풀이 해설
1세대인 경우는 "Rr" 값을 설정하므로 recursive 함수만 설명하겠다.
한 세대의 총 완두콩 개수는 4^n-1 개이다.
총 개수에서 0 ~ 1/4 범위는 "RR"이고 3/4 ~ 1 범위는 "rr"이다.
이러면 recursive에 3번째 줄 코드까지 이해가 될 것이다.

문제는 중앙 부분인데 잘 보면 반복되고 있다는 게 눈에 보일 것이다.
아래 그림에서 빨간색 부분이 다 똑같이 생겼다.

n세대에서 4등분했을 때 2, 3번째 덩어리 중 하나만 보면 덩어리 하나가 n-1세대인 것이다.
구간 별로 n - 1세대일 경우로 재귀를 사용해야 한다.

• 두번째 덩어리일 경우 첫번째 덩어리 개수만큼 번호를 빼준다. recursive(n - 1, p - cnt / 4);
• 세번째 덩어리일 경우 두번째 덩어리 개수만큼 번호를 빼준다. recursive(n - 1, p - cnt / 2);

함수 호출이 반복되면서 1, 4번째 덩어리는 리턴, 최악의 경우에는 2 세대가 됐을 때 빠져나올 수 있다.
탈출 조건이 2세대인 이유는 2 세대는 총 개수가 4개다.
즉 1, 4번째 덩어리 탈출 조건을 지나면 무조건 "Rr"일 수 밖에 없다.