C++ / 프로그래머스 / 1회 모의고사 - 유전법칙

문제

 

https://school.programmers.co.kr/learn/courses/20847/lessons/255902

프로그래머스

 

문제풀이

 

규칙만 찾고 재귀로 풀면 할만하다.

처음 시작은 "Rr"로부터 시작한다.

부모가 "RR"인 경우는 자식은 모두 "RR"이다.

부모가 "Rr"인 경우는 자식은 "RR", "Rr", "Rr", "rr"이다.

부모가 "rr"인 경우는 자식은 모두 "rr"이다.

 

[gen, idx]가 입력되면 gen이 2가 될 때까지 재귀를 돌린다.

부모를 찾아갈수록 idx는 4로 나눈다.

계속 재귀를 하다 gen이 2가 됐을 때, idx번째의 부모를 return 한다.

[2, 0]이라면 "RR"을, [2, 1], [2, 2]이라면 "Rr"을, [2, 3]이라면 "rr"을 return 한다.

그다음 3세대에서는 위에서 부모를 찾았으므로 부모에 대해 자식을 찾는다.

 

부모를 보고 idx번째의 자식을 찾아 return 한다.

계속 return 하다 처음 입력한 값의 성질을 찾게 되면 ret 벡터에 값을 입력한다.

 

코드

#include <string>
#include <vector>
using namespace std;

string type[4] = { "RR", "Rr", "Rr", "rr" };
string answer;

string find_parent(int gen, int idx) {
    if (gen == 1) {
        return "Rr";
    }
    else if (gen == 2) {
        return type[idx];
    }
    else {
        string parent = find_parent(gen - 1, idx / 4);
        if (parent == "RR") {
            return "RR";
        }
        else if (parent == "Rr") {
            return type[idx % 4];
        }
        else if (parent == "rr") {
            return "rr";
        }
    }
}

vector<string> solution(vector<vector<int>> queries) {
    vector<string>ret;
    for (int idx = 0; idx < queries.size(); ++idx) {
        ret.push_back(find_parent(queries[idx][0], queries[idx][1] - 1));
    }
    return ret;
}