[백준/파이썬][Silver IV] 피보나치 수 7 - 15624

[Silver IV] 피보나치 수 7 - 15624

문제 링크

성능 요약

메모리: 110576 KB, 시간: 100 ms

분류

다이나믹 프로그래밍, 수학

제출 일자

2025년 2월 6일 23:08:10

문제 설명

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 $F_n = F_n-1 + F_n-2 (n ≥ 2)$가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다.

풀이

def main() :
    n = int(input())
    a, b = 0, 1

    for _ in range(n) :
        a, b = b, (a+b) % 1_000_000_007
    print(a)

main()

전형적인 피보나치 수 문제이고 가장 일반적으로 쉬운 for 문 풀이로만 진행하였다. 

MOD = 1_000_000_007
def main() :
    n = int(input())
    dp = [0] * 1_000_001
    dp[1] = 1

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

    print(dp[n])
main()

두 번째는 다이나믹 프로그래밍을 활용해서 풀이를 진행하였고, 가장 대표적인 효율적인 두 풀이이다. 

그러나 지금 문제에 제시된 수식을 보게 되면

MOD = 1_000_000_007

def fibo(n) :
    if n <= 1 :
        return n

    else :
        num = (fibo(n-2) + fibo(n-1)) % MOD
        return num
def main() :
    n = int(input())
    res = fibo(n)
    print(res)

main()

이런 식으로 구현이 가능하고, 이는 백준 기준으로는 RecursionError 가 나오게 된다. 

로컬에서 돌려보니 첫번째 예시였던 10은 잘 나오는데 두번째 예시인 1,000 은 빠르게 도출되지 않았다. 

따라서 재귀를 활용한 방법은 빠르게 접근이 가능하긴 하나, 적절하지 못한 모습이다. 혹시나 궁금하다면 직접 로컬에 구현해보길 바란다.