[PCCP 모의고사 #1] 3번 - 유전법칙

RR(4)라고 표기한건 [RR, RR, RR, RR]을 의미 그냥 해당 seq(유전자 형질) 갯수 나타낸것입니다.

 

처음에 문자 그대로 그냥 점화식으로 풀었는데 시간초과 떠서 다시품

dp[n] = [ RR(4**(n-2)), dp[n-1], dp[n-1], rr(4**(n-2))] (n>1)

 

보면 앞에 RR과 맨뒤 rr은 갯수가 많으니까 ["RR", "RR", "RR", "RR", ....]

이렇게 문자 그대로 list에 넣고 점화식 돌리면 아주 오래걸림

 

보통 그냥해서 시간초과 나면 비슷하거나 같은거 끼리 묶으면 해결 가능

ex)  ["RR", "RR", "RR", "RR"] => RR(4)

 

그래서 숫자로 대체

1 세대 => Rr => 나중에 예외처리 해줌

2 세대 => RR(1), Rr(2), rr(1)

3 세대 => RR(5), Rr(2), rr(1), RR(1), Rr(2), rr(5)

4 세대 => RR(21), Rr(2), rr(1), RR(1), Rr(2), rr(5), RR(5), Rr(2), rr(1), RR(1), Rr(2), rr(21)

이런식으로 list구성

 

RR, Rr, rr 반복인거 확인

이후에는 p가 어떤 seq인지 찾으면 끝

 

 

ex) [n=4,p=24]

4세대 에서

RR(21), Rr(2), rr(1), RR(1), Rr(2), rr(5), RR(5), Rr(2), rr(1), RR(1), Rr(2), rr(21)

p가 24면

list에서 순차적으로 해당 seq갯수를 뺴줌

p -= RR(21)  => [p=3] 

p -= Rr(2)    => [p=1]

p -= rr(1)    => [p=0]

최초로 0 이하가 되면 해당 seq임

p - 21 -2 -1 <= 0

따라서 rr

def solution(queries):
    answer, seq_maps, max_n = [], [], 0
    seq_maps.append(["Rr"])
    seq_maps.append([1,2,1])
    
    for querie in queries:
        if max_n < querie[0]: max_n = querie[0]
    
    if max_n > 2:
        for i in range(3, max_n+1):
            s_map = []
            s_map.append(4**(i-2)+seq_maps[i-2][0])
            s_map.extend(seq_maps[i-2][1:])
            s_map.extend(seq_maps[i-2][:-1])
            s_map.append(4**(i-2)+seq_maps[i-2][-1])
            seq_maps.append(s_map)
            
    seq = ["RR", "Rr", "rr"]
    for querie in queries:
        n, p = querie[0], querie[1]
        if n == 1:
            answer.append("Rr")
        else:
            c = 0
            for seq_cnt in seq_maps[n-1]:
                p -= seq_cnt
                if p <= 0:
                    answer.append(seq[c])
                    break
                c += 1
                if c == 3: c = 0
    return answer