문제

n번째의 피보나치 수를 1234567 로 나눈 나머지를 구하여라.
n 은 2 <= n <= 10000 인 자연수.

접근법

피보나치 수열 치고는 n이 굉장히 크므로 재귀함수를 이용한 접근법은 런타임 에러가 난다. 따라서 Dynamic Programming 으로 접근하였다.

Code

def solution(n):
    m = 1234567
    febo_list = [0]
    for i in range(1,n+1):
        if i <= 1:
            febo_list.append(1)
        else:
            febo_list.append(febo_list[i-2] + febo_list[i-1])
    
    return febo_list[-1] % m

다른사람 풀이

def fibonacci(num):
    a,b = 0,1
    for i in range(num):
        a,b = b,a+b
    return a