백준 파이썬 11444번 피보나치 수 6 (Today I Learn 2025.11.04)

백준 파이썬 공부 2025.11.04
11444번 피보나치 수 6 (골드 2)

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

이를 식으로 써보면 Fn = Fn-1 + Fn-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번째 피보나치 수를 구하는 프로그램을 작성하시오.

2. 입력
첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

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

4. 문제 풀이
문제 자체는 간단한 재귀문제로 보이나.. 수의 제한범위가 심상치 않아보인다
일단 원래 방식대로 풀어보자

>>코드1. 재귀 이용 : 런타임 에러

"""
11444번 피보나치 수 6
입력 : n (피보나치수 번호)
출력 : fibo (n번째 피보나치 수)
"""

n = int(input())

def fibo(n):
    if n == 0 or n == 1:
        return n
    return fibo(n-1) + fibo(n-2)

print(fibo(n))

뭐 당연한 결말이였던거 같다...
그러면 다이나믹 프로그래밍을 이용해보자..

>>코드2. 동적프로그래밍 이용 : 메모리 초과

"""
11444번 피보나치 수 6
입력 : n (피보나치수 번호)
출력 : fibo (n번째 피보나치 수)
"""

n = int(input())

def fibo(n):
    dp = [0, 1]
    for i in range(2, n+1):
        dp.append(dp[-1] + dp[-2])
    return dp[n]

print(fibo[n])

그렇다.. 메모리 초과 엔딩이다.
그렇다면,,? 숫자를 2개만 저장하며 갱신하는 방식으로 해보자

>>코드 3. 반복문 + 공간 최적화 DP : 시간초과

"""
11444번 피보나치 수 6
입력 : n (피보나치수 번호)
출력 : fibo (n번째 피보나치 수)
"""

n = int(input())

def fibo(n):
    f = [0, 1]
    if n < 2:
        return f[n]
    for i in range(n):
        f[0], f[1] = f[1], f[0] + f[1]
    return f[0]
    
print(fibo(n))

그렇다.. 수가 너무 크기 때문에 이것도 시간초과가 나온다.
따라서 새로운 방법을 찾아내야 한다.

빠른 거듭제곱 (분할정복) 을 이용한다.
행렬의 곱셈을 이용하여, 피보나치 수를 구한다.
1 1
1 0  행렬을 거듭제곱하면 피보나치 수가 나온다.

 

방식이 더하기에서 곱하기로 바뀌었으므로 분할 정복이 가능하다.

- 거듭제곱 수p가 짝수면 : p//2 거듭제곱 x p//2 거듭제곱
- 거듭제곱 수p가 홀수면 : M [[1, 1], [1, 0]] x p//2 거듭제곱 x p//2 거듭제곱

또한 행렬의 곱셈 시 매번 MOD (1,000,000,007) 로 나누어 수가 너무 커지는 것을 방지한다.

>>코드 4. 정답입니다.

"""
11444번 피보나치 수 6
입력 : n (피보나치수 번호)
출력 : fibo (n번째 피보나치 수)
"""

n = int(input())
fibo = [0, 1]
MOD = 1000000007

def fibo(n):
    def mat_mult(A, B):
        return [
            [(A[0][0]*B[0][0] + A[0][1]*B[1][0]) % MOD,
             (A[0][0]*B[0][1] + A[0][1]*B[1][1]) % MOD],
            [(A[1][0]*B[0][0] + A[1][1]*B[1][0]) % MOD,
             (A[1][0]*B[0][1] + A[1][1]*B[1][1]) % MOD]
        ]
    
    def mat_pow(M, p):
        if p == 1:
            return M
        if p % 2 == 0:
            half = mat_pow(M, p//2)
            return mat_mult(half, half)
        else:
            return mat_mult(M, mat_pow(M, p-1))
        
    if n == 0:
        return 0
    
    M = [[1, 1], [1, 0]]
    result = mat_pow(M, n)
    return result[0][1]
    
print(fibo(n))

5. 문제 링크
https://www.acmicpc.net/problem/11444