[BOJ] 11444. 피보나치 수 6

 

백준 문제 주소 :

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

11444번: 피보나치 수 6

 

알고리즘은 수학과 밀접한 관련이 있다는 걸 깨닫게 해주는 문제였습니다... (불태웠어,,,,)

피보나치 수는 재귀로 쉽게 풀 수 있지만은,

이 문제는 10조도 아닌 10경번째 피보나치 수를 구해야되기 때문에 시간이 정말 중요하더라구요!

 

 

처음은 그냥 점화식 'f(n) = f(n-1) + f(n-2)' 를 썼는데,

와... 50번째도 제대로 안 돌아가더라구요 ㅠㅠ

그래서 생각난 코드!

def fibo2(n):
    f = [0, 1]

    for i in range(2, n + 1):
        f.append(f[i - 1] + f[i - 2])
        f[i] = f[i] % 1000000007
    return f[n]


s = int(input())
print(fibo2(s))

 

리스트에 값을 저장해서 DP형식으로 풀었습니다.

하지만... ㅠㅠㅠㅠ 이거도 안되요. 흑흑

 

그렇게 찾아보다 나온 것은.....

행렬곱!!

 

피보나치에 행렬곱으로 푸는 방법이 있더라구요.

그래서 만든 코드는 이렇습니다.

import math

def fibo(n, f1, f2) :
    for i in range(n) :
        f2, f1 = (f1 + f2) % 1000000007, f2
    return f2

def fibo2(n):
    f1, f2, f3 = 0, 1, 1
    for i in range(1, n + 1):
        f3, f2, f1 = (f3*f3 + f2*f2) % 1000000007, (f3*f2 + f2*f1) % 1000000007, (f2*f2 + f1*f1) % 1000000007
    return (f2, f3)

s = int(input())
log_s = math.floor(math.log2(s))
rest_s = s - 2**log_s - 1
a = fibo2(log_s)
if rest_s == -1 :
    print(a[0])
else :
    print(fibo(rest_s, a[0], a[1]))

 

그런데 또 실패!!! 왜냐면 행렬곱을 다 쓴게 아니라

행렬곱으로 숫자를 0부터 2의 제곱수들까지 올라가서

n에서 제일 가까운 2의 제곱수에서 n을 찾아가기 때문이었습니다.

 

그래서 찾은 방법!!

 

이걸 반대로 생각하니까 정말 쉽더라구요.

n에서 부터 내려오면 정말 행렬곱으로만 풀 수 있는 것이었습니다!!

코드는 이렇습니다.

def fibo(n):
    if dict_fibo.get(n) != None:
        return dict_fibo[n]
    else:
        if n % 2:
            f = (fibo((n + 1) // 2) % 1000000007) ** 2 + (fibo(n // 2) % 1000000007) ** 2
        else:
            f1 = fibo(n // 2 - 1) % 1000000007
            f2 = fibo(n // 2) % 1000000007
            f = ((f1 + f2) * f2 + f2 * f1) % 1000000007

        dict_fibo[n] = f % 1000000007
        return f % 1000000007


s = int(input())
dict_fibo = {0: 0, 1: 1}
print(fibo(s))

 

근데 사실 이 코드를 이해하려면 처음 말했듯이 수학적 사고가 무조건 필요합니다.

행렬곱 이해와 그 행렬곱을 조지다보면 나오는 식들이 여러개가 있습니다.

그 식들 완전 여러개 만들어 보다보면 이런코드를 만들 수 있습니다 ㅎ.... 흐악 ㅠㅠ

하루동안 진짜 머리 싸매고 계속 봤네여, 다른 식도 가능하니깐 다들 한번 다른 식으로 도전해보세욥 ㅎㅎ