[프로그래머스] 피보나치 수 - python

피보나치 수

문제 설명

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한사항

• n은 2 이상 100,000 이하인 자연수입니다.

풀이

입력값이 크기 때문에 dp로 구현해야하는 것을 알 수 있다.

def solution(n):
    answer = 0
    fibo = [0] * (n + 1)
    fibo[1] = 1
    
    for i in range(2, n + 1):
        fibo[i] = fibo[i - 2] + fibo[i - 1]
    return fibo[n] % 1234567

변수 2개만 써도 해결할 수 있다.

def solution(n):
    answer = 0
    a, b = 1, 1
    
    for i in range(3, n + 1):
        a, b = b, (a + b)
        
    return b % 1234567