코딜리티 lesson13 (피보나치), FibFrog, Ladder

FibFrog

[참고풀이]

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    target = len(A)
    if target == 0:
        return 1
    
    fibo = [0,1]
    preNum1 = fibo[-1]
    preNum0 = fibo[-2]

    while fibo[-1] <= target+1:
        fibo.append(preNum0 + preNum1)
        preNum1 = fibo[-1]
        preNum0 = fibo[-2]

    ret = -1
    arrive = False
    Q = [(-1, 0)]
    visit = [0] * (target+1)

    while Q:
        pos = Q[0][0]
        cnt = Q[0][1]
        del Q[0]

        if arrive:
            break
        
        for f in fibo:
            next_pos = pos + f
            if next_pos == target:
                arrive = True
                ret = cnt + 1
                break
            if next_pos < target and not visit[next_pos] and A[next_pos] == 1:
                Q.append((next_pos, cnt+1))
                visit[next_pos] = 1
    return ret

Ladder

[참조풀이]

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

import math

def solution(A, B):
    N = len(A)
    maxP = math.pow(2, 30)

    fibo = [0,1,2]

    for i in range(3, N+1):
        fibo.append(int((fibo[i-1] + fibo[i-2]) % maxP))
        
    res = []
    for i in range(N):
        res.append(int(fibo[A[i]] % math.pow(2, B[i])))
    
    return res