멘델은 완두콩을 이용하여 7년간 실험한 결과, 다음과 같은 특별한 법칙을 발견하였습니다.
멘델의 법칙을 공부한 진송이는, 직접 완두콩의 자가 수분 실험을 진행했습니다. 진송이의 실험에서 완두콩 한 개를 자가 수분한 결과는 다음과 같습니다.
잡종 완두콩(Rr) 1대부터 시작한 가계도로 그려보면 그림 2와 같습니다.
진송이는 이러한 완두콩의 자가 수분 실험 결과를 정리하고 싶어합니다. 하지만, 세대를 거듭할수록, 완두콩의 수가 너무 많아져 모든 가계도를 기록하기 어려워졌습니다. 진송이는 가계도를 전부 기록하는 것 대신, 완두콩의 세대와 해당 세대에서 몇 번째 개체인지를 알면 형질을 바로 계산하는 프로그램을 만들려 합니다.
각 세대에서 맨 왼쪽 개체부터 첫 번째, 두 번째, 세 번째, ...개체로 나타냅니다. 예를 들어 그림 2에서 2세대의 네 번째 개체의 형질은 "rr"이며, 3세대의 9번째 개체의 형질은 "RR"입니다.
형질을 알고 싶은 완두콩의 세대를 나타내는 정수 n
과, 해당 완두콩이 세대 내에서 몇 번째 개체인지를 나타내는 정수 p
가 2차원 정수 배열 queries
의 원소로 주어집니다. queries
에 담긴 순서대로 n
세대의 p
번째 개체의 형질을 문자열 배열에 담아서 return 하도록 solution 함수를 완성해주세요.
queries
의 길이(쿼리의 개수) ≤ 5queries
의 원소는 [n
, p
] 형태입니다.
n
≤ 16p
≤ 4n-1queries | result |
---|---|
[[3, 5]] | ["RR"] |
[[3, 8], [2, 2]] | ["rr", "Rr"] |
[[3, 1], [2, 3], [3, 9]] | ["RR", "Rr", "RR"] |
[[4, 26]] | ["Rr"] |
입출력 예 #1
입출력 예 #2
입출력 예 #3
입출력 예 #4
- n세대 k번째 개체의 부모는 n-1세대의 ceil(k/4)번째 개채다.
- n세대 k번째 개체의 2세대 조상은 ceil(k / (4^(n-2)))번째 개체다.
- n세대 k번째 개체의 g세대 조상은 ceil(k / (4^(n-g)))번째 개체다.
- 조상중 순종이 있다면 자식은 모두 순종이다.
- 잡종의 자식은 항상 RR, Rr, Rr, rr이다.
- 부모가 잡종이고 k번째 개체라면 k를 4로 나눈 나머지로 품종을 알 수 있다.
function solution(queries) {
const hybrid = "Rr";
const round = "RR";
const wrinkle = "rr";
const child = [round, hybrid, hybrid, wrinkle];
return queries.map((v) => {
//2세대 부터 내려오면서 검사한다.
for (let i = v[0] - 2; i >= 0; i--) {
const parent = child[(Math.ceil(v[1] / 4 ** i) - 1) % 4];
if (parent !== hybrid) return parent;
}
return hybrid;
});
}