1. 관련 문제 🎯
문제 : 프로그래머스 유전법칙 🪴
2. 문제 소개 🧩
진송이의 실험에서 완두콩 한 개를 자가 수분한 결과는 다음과 같습니다.
1️⃣ 각 완두콩은 자가 수분해서 정확히 4개의 완두콩 후손을 남긴다.
2️⃣ 잡종 완두콩(Rr)은 자가 수분해서 첫째는 RR, 둘째와 셋째는 Rr, 넷째는 rr 형질의 후손을 남긴다.
3️⃣ 순종 완두콩(RR, rr)은 자가 수분해서 자신과 같은 형질의 후손을 남긴다.
잡종 완두콩(Rr) 1대부터 시작한 가계도로 그려보면 아래의 그림과 같습니다.
그림 출처 : https://school.programmers.co.kr/learn/courses/15008/lessons/121685
➡️ 완두콩의 세대와 해당 세대에서 몇 번째 개체인지를 알면 형질을 바로 계산하려고 한다.
- 각 세대에서 맨 왼쪽 개체부터 첫 번째, 두 번째, 세 번째, ...개체로 나타냅니다.
- 예를 들어 위의 그림에서 2세대의 네 번째 개체의 형질은 "rr"이며, 3세대의 9번째 개체의 형질은 "RR"입니다.
3. 문제 풀이 🖌️
☝️ 이 문제는 가계도를 for문을 사용하여 vector<int>graph[12]에 넣으면서 세대별로 하나의 배열에 넣을 수 있지만 이렇게 구하는 경우 2의 16 제곱까지 나오므로 시간 초과가 발생한다!
따라서 구하고자 하는 콩의 세대와 위치를 입력받으면, 해당 콩의 부모를 찾는 방식인 재귀를 사용하여 문제의 답을 찾아야 한다!!
☝️ 먼저, 구하고자 하는 콩의 부모들을 찾아보자!
- 이때, 세대가 1이 최소이므로 세대가 1이 나올 때까지 부모를 구한다.
(재귀의 종료 조건이 된다.) - 구하고자 하는 콩의 번호가 (3,5)인데, 실제 인덱스는 5가 아닌 4이므로 세대 중 위치를 5-1=4의 값으로 바꿔서 생각해야 한다.
- 세대 중 위치(idx)는 부모(idx/4)를 찾는 데에 사용되고, 한 부모에서의 자식 번호(idx%4)는 자식의 형질을 알아내는 데에 사용된다,
자식 : 세대 = 3 , 세대 중 위치 = 4, 한 부모에서의 자식 번호 = 4%4 = 0
➡️ 부모 1: 세대 2, 세대 중 위치 : 4/4 = 1, 한 부모에서의 자식 번호 : 1%4 = 1
➡️ 부모 2 : 세대 1, 세대 중 위치 : 1/4 = 0
✌️ 이제, 구하고자 하는 콩의 부모들로부터 자식의 형질을 알아내자!
1️⃣ 부모 2 : 세대 1, 세대 중 위치 : 0 ➡️ “Rr” (세대 1은 “Rr”만 존재한다.)
2️⃣ 부모 1 : 세대 2, 세대 중 위치 : 1, 한 부모에서의 자식 번호: 1
➡️ 위에서 구한 부모2의 형질 “Rr”의 자식 중 1번인 “Rr”
3️⃣ 자식 : 세대 3, 세대 중 위치 : 4, 한 부모에서의 자식 번호 : 0
➡️ 위에서 구한 부모1의 형질 “Rr”의 자식 중 0번인 “RR”
4. 전체 코드 🔑
#include <string>
#include <vector>
using namespace std;
string beans(int generation, int idx){
if(generation == 1) return "Rr"; //종료 조건
string parent_bean = beans(generation-1, (idx/4)); //부모의 형질을 알아낸다.
//부모의 형질을 바탕으로 자신의 형질을 알아낸다.
if(parent_bean == "RR") return "RR";
else if (parent_bean == "rr") return "rr";
else {
int bean_sort = idx%4;
if(bean_sort == 0) return "RR";
if(bean_sort == 1 or bean_sort == 2) return "Rr";
return "rr";
}
}
vector<string> solution(vector<vector<int>> queries) {
vector<string> answer;
for(int i=0; i<queries.size(); i++){
answer.push_back(beans(queries[i][0], queries[i][1]-1));
}
return answer;
}5. 결과 🏆
