PGS 유전법칙

태그

구현

재귀

URL

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

문제 설명

•

완두콩의 유전 규칙에 따라 특정 세대와 위치의 완두콩 형질을 계산하는 문제

예제 입력/출력

queries	result
[[3, 5]]	["RR"]
[[3, 8], [2, 2]]	["rr", "Rr"]
[[3, 1], [2, 3], [3, 9]]	["RR", "Rr", "RR"]
[[4, 26]]	["Rr"]

제약 조건

•

1≤∣queries∣≤51 ≤ |queries| ≤ 51≤∣queries∣≤5

•

quereis의 원소는 [n, p] 형태

◦

1≤n≤161 ≤ n ≤ 161≤n≤16 (세대)

◦

1≤p≤4n−11 ≤ p ≤ 4^{n-1}1≤p≤4n−1 (개체)

문제 풀이

접근1 브루트 포스 - 상한 O(416)O(4^{16})O(416)

접근2 재귀 - 상한 O(5⋅16)O(5 \cdot 16)O(5⋅16)

풀이 코드

•

재귀 - 상한 O(5⋅16)O(5 \cdot 16)O(5⋅16)

def dfs(n, p):
    # Base Case
    if n == 1:
        return "Rr"
    
    # Recursive Case
    parent_idx = (p - 1) // 4 + 1 # 1-index
    parent = dfs(n - 1, parent_idx) # 부모의 형질 계산
    child_idx = (p - 1) % 4 # 부모의 자식 중 몇 번째인지 계산
    
    if parent == "RR":
        return "RR"
    elif parent == "rr":
        return "rr"
    else:  # parent == "Rr"
        return ["RR", "Rr", "Rr", "rr"][child_idx]
    

def solution(queries):
    result = []
    
    for query in queries:
        result.append(dfs(query[0], query[1]))
    
    return result
Python
복사

참고 자료

TISTORY[Programmers/Python] 유전 법칙