[Baekjoon] 백준 11444번 Python

백준 11444번

사전지식 : 피보나치 수열(짝수, 홀수 점화식), 동적프로그래밍(Dynamic Programming), 메모이제이션(memoization)

피보나치 수의 또다른 규칙성(점화식)

from collections import defaultdict

def f(num):
    if num <= 2:
        return memo[num]
    elif memo[num] > 0:
        return memo[num]

    else:
        half = num // 2
        
        if num % 2 == 0:
            h0 = f(half)
            h1 = f(half-1)
            memo[num] = ((2*h1 + h0)*h0)%1000000007
            return memo[num]
            
        else: 
            h0 = f(half+1)
            h1 = f(half)
            memo[num] = (h0**2 + h1**2)%1000000007
            return memo[num]
            

n = int(input())

memo = defaultdict(int)
memo[1],memo[2] = 1,1

print(f(n))

코드 설명

1. 입력값이 매우 크기 때문에 피보나치 수의 또다른 규칙성(점화식)을 찾아야함
   
   
2. $f_n = f_{n-1} + f_{n-2} = 2f_{n-2} + f_{n-3} (f_{n-1} = f_{n-2} + f_{n-3})$로 표현 할 수 있음
   
   
3. 이런 식으로 $\frac{n}{2}$까지 가게 되면
   $n \div 2 = 0$ 일때 : $F_n = F_{\frac{n}{2}+1}^2 - F_{\frac{n}{2}-1}^2$
   $n \div 2 == 1$ 일때 : $F_n = F_{\frac{n}{2}+1}^2 + F_{\frac{n}{2}-1}^2$ 라는 규칙성을 발견 할 수 있음
   
   
4. 먼저 시간초과를 방지하기 위해 딕셔너리로 메모제이션를 활용함
   
   
5. 메모이제이션(memoization) : 계산한 결과를 저장해 두고 나중에 같은 계산이 필요할 때 다시 계산하지 않고 저장된 결과를 사용하는 것
   
   
6. 일반 딕셔너리가 아닌 defaultdict을 사용하는 이유 : defaultdict는 존재하지 않는 키에 접근할 때 예외를 발생시키지 않고 기본값을 반환함
   
   
7. 가독성을 위해 함수로 표현
   
   
8. 피보나치 수의 1,2번째는 1이기 때문에 n≥2일 경우 1을 반환
   
   
9. defaultdict(int)의 기본값은 0이기 때문에 0이 아닌 값일 경우 이미 계산한 값이기에 그대로 반환 (memoization)
   
   
10. n이 짝수일 경우 (h0 = fn, h1 = fn-1로 입력) 짝수일때의 점화식 적용후 1000000007로 나눈값 반환
    
    
11. n이 홀수일 경우 (h0 = fn+1, h1 = fn로 입력) 홀수일때의 점화식 적용후 1000000007로 나눈값 반환
    
    
12. n을 입력 받음
    
    
13. 딕셔너리 형태로 피보나치 수의 값을 받을 수 있도록 변수 설정
    
    
14. 1번째수와 2번째수는 1로 입력
    
    
15. 함수를 통해 나온 값 출력