[PCCP 모의고사] 3번 유전법칙 c++

문제 링크

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

프로그래머스

 

문제 풀이

우선, 시간 제한 사항에 주목하자. 

 

1 ≤ queries의 길이(쿼리의 개수) ≤ 5
queries의 원소는 [n, p] 형태입니다.
1 ≤ n ≤ 16
1 ≤ p ≤ 4^(n-1)

 

최대 p는 4^(n-1)이다. 즉 4^15은 아래와 같이 10억을 넘는 연산이 발생하기에, 시간초과가 발생한다.

그렇기에 완전탐색은 해결책이 아니다. 이 경우,   4로 나눈 몫, 그리고 나머지를 활용하여 문제를 해결할 수 있다.

 

 

3번째 세대( 0~15) 에서 4로 나눈 몫은 아래와 같이 규정할 수 있다.

0~3 -> 0
4~7 -> 1
8~11 -> 2
12~15 ->3

즉, 해당 세대의 최상위 부모에서 몇번쨰 자식에서 파생되었는지를 구할 수 있다. ( 이 부분이 이해가 가지 않는다면 직접 해보며 이해하는 것을 추천한다. )

이 과정을 반복하면서, 1-> n세대까지 가는 과정에서 본인이 몇번째 자식에서 파생되었는지 구하면서 가짓수를 따져 나간다면, 손쉽게 답이 완성된다. 

 

정답 코드

#include <string>
#include <vector>
#include<math.h>
#include<iostream>
using namespace std;


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



vector<string> solution(vector<vector<int>> queries) {
    vector<string> answer;
    int n,p;
    for(int i=0;i<queries.size();i++){
        n=queries[i][0]-1;//1
        p=queries[i][1]-1;//1
        if(n==0||n==1){
            if(n==0)answer.push_back("Rr");
            else if(n==1){
                answer.push_back(bb[p]);
            }
            continue;
    }
       int st=pow(4,n-1);
        int now,nxt;
        int type=1;
        while(st>=1){
            now=p/st;
            if(type==0){
                type=0;
            }
            else if(type==1||type==2){
                type=now;
            }
            else if(type==3){
                type=3;
            }
            p%=st;
            st/=4;
        }
        
        answer.push_back(bb[type]);
      //  printf("%d\n",mod);
    }
    
    return answer;
}