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

🔗 문제 링크

프로그래머스

📂 분류

DP

💡 풀이

피보나치 수는 DP의 대표적인 문제이다.

피보나치 수는 DP를 사용하지 않고 재귀 함수로 풀 경우 이미 계산된 값을 또 계산하기 때문에 스택 버퍼오버플로우가 발생할 수 있다. 때문에 DP를 사용하여 값을 구한다.

 

점화식은 다음과 같다

• f[i] = f[i - 1] + f[i - 2]

위 점화식을 이용해 구현하면 문제를 해결할 수 있다.

💻 코드

MOD = 1234567


def solution(n):
    global MOD

    fibo = [0] * (n + 1)
    fibo[1] = 1

    for i in range(2, n + 1):
        fibo[i] = (fibo[i - 2] + fibo[i - 1]) % MOD

    return fibo[n]