[Codility] 13.2 Ladder

Ladder 문제 풀기

$K$번째 사다리에 오는 방법의 수는 $K-1 \, , K-2$번째 사다리에서 오는 방법밖에 없다. $K$번째 사다리에 오는 방법의 수를 $a_k$라 하면 $a_k=a_{k-1}+a_{k-2}$이므로 피보나치 수열 그 자체다. 하지만 초기값 $a_1=1, a_2=2$임에 주의한다.

범위가 $50,000$이하이므로 반복문으로 해도 충분히 풀 수 있다.
$(b+c)\mod m = (b \mod m + c \mod m) \mod m$에 유의한다.

def solution(A, B):
    fibo = [0] * 50001
    mod = pow(2, 30)
    fibo[1] = 1
    fibo[2] = 2
    for i in range(3, 50001):
        fibo[i] = (fibo[i - 1] % mod + fibo[i - 2] % mod) % mod
    
    ret = []
    for i in range(len(A)):
        ret.append(fibo[A[i]] % pow(2, B[i]))

    return ret