PCCP 모의고사1회 3번

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

프로그래머스

 

풀이과정

 

1. 부모의 유전형질 찾기

(n,p)의 부모는 (n-1, (p-1)/4 + 1) 입니다.

 

2. 부모가 'RR' 이면 자식도 'RR', 부모가 'rr' 이면 자식도 'rr' 입니다.

부모가 'Rr'이라면 자식은 4가지 형질 {"RR","Rr","Rr","rr"} 에서 자신의 위치에 해당하는 값입니다.

자신의 위치는 (p-1)%4 로 계산할 수 있습니다.

    String[] tmp = {"RR","Rr","Rr","rr"};
    
    String solve(int n, int p){
        if(n==1) return "Rr";
        
        String parent = solve(n-1,(p-1)/4+1);
        
        if(!parent.equals("Rr")) return parent;
        
        return tmp[(p-1)%4];
        
    }

 

 

알게된 점

• 메모리제이션 배열의 크기가 너무 큰 경우 dp를 못 쓰는 경우가 있다는 것을 알게되었습니다.
  • 해당 문제에서 메모리제이션 배열을 만든다면 크기가 ( 16 x 1,000,00,000 ) 인 배열이 되기 때문에 메모리가 초과가 발생합니다.

 

코드

import java.util.*;

// n세대 p번째 형질
class Solution {
    String[] tmp = {"RR","Rr","Rr","rr"};
    
    String solve(int n, int p){
        if(n==1) return "Rr";
        
        String parent = solve(n-1,(p-1)/4+1);
        
        if(!parent.equals("Rr")) return parent;
        
        return tmp[(p-1)%4];
        
    }
    
    public String[] solution(int[][] queries) {
        String[] answer = new String[queries.length];
        
        for(int i=0;i<queries.length;i++){
            int n,p;
            n = queries[i][0];
            p = queries[i][1];
            answer[i] = solve(n,p);
        }
        
        return answer;
    }
}