백준 11444 - 피보나치 수 6 (Python)

 

 

문제

https://www.acmicpc.net/problem/11444

11444번: 피보나치 수 6

풀이

import sys
sys.setrecursionlimit(10**8)
memo = {}
memo[0] = 0
memo[1] = 1
memo[2] = 1

def dp(i):
    if i not in memo:
        if i%2==0:
            memo[i] = (dp(i//2) * (dp(i//2) + 2*dp(i//2-1)))%1_000_000_007
        else:
            memo[i] = (dp(i//2)**2 + dp(i//2+1)**2)%1_000_000_007
    return memo[i]

n = int(input())
print(dp(n))

일단 DP문제이긴 한데, 도가뉴 항등식에 대한 배경지식이 있어야 한다.

 

도가뉴 항등식(d'Ocagne's identity)란 피보나치 수열에서 성립하는 아래의 항등식을 말한다.

$$ F_{m+n}=F_{m-1}F_{n}+F_{m}F_{n+1} $$

 

이 항등식을 짝수(m대신 n대입)와 홀수(m 대신 n+1대입)로 나누어서 변형하면 아래의 두 항등식이 나오게 된다.

$$ F_{2n}=F_{n}(F_{n}+2F_{n-1}) $$

$$ F_{2n+1}=F^{2}_{n}+F^{2}_{n+1} $$

 

dp 함수 내에서 i 값의 짝수 홀수를 판별하여 해당하는 항등식을 이용하여 값을 계산하고 해당 값을 1,000,000,007로 나누어 저장해둔 후 사용하는 방식으로 구현했다.

 

미리 1,000,000,007을 나누어서 저장해도 되는 이유는 저번 15988번 문제 풀이에서도 잠깐 언급했던 모듈 산술연산의 분배법칙 때문이다.

덧셈, 뺄셈, 곱셈에 대한 모듈러 산술 연산 분배 법칙은 아래와 같다.

$$ (A \pm B) mod C = (A mod C \pm B mod C) mod C $$

$$ (A * B) mod C = (A mod C * B mod C) mod C $$

 

나눔셈의 경우 역원을 이용하여 표현하는데, 자세한건 다음에 관련 문제를 풀면 알아보겠다.

(아마 13172번 - Σ문제를 풀것 같음)