PCCP 모의1회 3번

문제 링크 :

https://school.programmers.co.kr/learn/courses/15008/lessons/121685

나의 소스 코드 :

#include <string>
#include <vector>

using namespace std;

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

string find_st(int n, int p, int idx)
{
    if(n == 2)
    {
        return Rr[idx-1];
    }
    
    int parent_n = n-1;
    int parent_p = p%4 == 0 ? p/4 : p/4+1;
    int parent_idx = parent_p%4 == 0 ? 4 : parent_p%4;
    string parent = find_st(parent_n, parent_p, parent_idx);
    
    if(parent == "RR")
    {
        return "RR";
    }
    else if(parent == "Rr")
    {
        return Rr[idx-1];
    }
    else
    {
        return "rr";
    }
}

vector<string> solution(vector<vector<int>> queries) {
    vector<string> answer;
    
    for(int i=0;i<queries.size();i++)
    {
        int n = queries[i][0];
        int p = queries[i][1];
        int idx = p%4 == 0 ? 4 : p%4;
        
        if(n == 1 && p == 1){
             answer.push_back("Rr");
        }
        else{
            answer.push_back(find_st(n, p, idx));
        }
    }
    
    return answer;
}

재귀를 통해 해당 콩의 인덱스와 그 조상을 찾아가는 문제였다.
아마 바로 재귀임을 파악하는게 우선이지 않았을까 한다. 다른 문풀도 재귀를 사용하였다.

인덱스의 효율

하지만 나와 다른 점은 (나의 개선점은) 인덱스에서 나왔다.
문제에서 나온대로 1,2,3,4번째로 인덱스를 지정하니, 소스가 길어졌다. 삼항식을 사용하는 것에서 볼 수 있다.
예시
3세대 16번째와 15번째의 조상은 2세대 4번째이다.
여기서 15/4는 3이겠지만, 16/4는 4이다. 단순 나눗셈 연산으로 일반화가 어렵다. 하지만, 만약 16번째는 15, 15번째는 14 (즉, 1번째는 0)으로 지정했으면 훨씬 코드의 가독성이 좋았을 것 같다.

재귀의 기준

find_st( ) 함수의 매개변수를 어떻게 보낼지 결정하는데 많은 시간이 걸렸다.
예를 들어 n, p가 조상의 것 그리고 idx가 그 자식의 것으로 할지 모두 자식의 것으로 할지
결국 나는 후자인 모두 자식의 것으로 하였다.
사실 상 idx는 p로 계산을 하는 것이므로 굳이 넘길 변수가 아니었고, 1세대까지 갈 필요 없이 2세대에서 멈춰도 된다는 것을 나중에 깨달았다.

고친 소스 코드

#include <string>
#include <vector>

using namespace std;

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

string find_st(int n, int p)
{
    if(n == 2)
    {
        return Rr[p%4];
    }
    
    int parent_n = n-1;
    int parent_p = p/4;
    string parent = find_st(parent_n, parent_p);
    
    if(parent == "RR")
    {
        return "RR";
    }
    else if(parent == "Rr")
    {
        return Rr[p%4];
    }
    else
    {
        return "rr";
    }
}

vector<string> solution(vector<vector<int>> queries) {
    vector<string> answer;
    
    for(int i=0;i<queries.size();i++)
    {
        int n = queries[i][0];
        int p = queries[i][1];
        
        if(n == 1 && p == 1){
             answer.push_back("Rr");
        }
        else{
            answer.push_back(find_st(n, p-1));
        }
    }
    
    return answer;
}