백준 11444번 피보나치 수 6

백준 11444번 피보나치 수 6 문제이다. 

 

문제는 다음과 같다. 

 

문제만 봤을때는 이게 왜 분할정복 분류지? 걍 하면 되겠는데? 하고 했다가 메모리 초과, 시간초과가 발생했다...

찾아보니 행렬을 이용한 방법이 있었다. 

 

 

코드는 다음과 같다. 

import sys


def mat_pow(mat, n):
    if n == 0:
        return mat
    elif n == 1:
        return mat
    else:
        tmp = mat_pow(mat, n//2)
        if n % 2 == 0:
            result = mul(tmp, tmp)
        else:
            a = [1, 1, 1, 0]
            result = mul(mul(tmp, tmp), mat)
    return result


def mul(a, b):
    c = [(a[0] * b[0] + a[1] * b[2]) % 1000000007, (a[0] * b[1] + a[1] * b[3]) % 1000000007,
         (a[2] * b[0] + a[3] * b[2]) % 1000000007, (a[2] * b[1] + a[3] * b[3]) % 1000000007]
    return c


n = int(sys.stdin.readline().strip())
mat = [1, 1, 1, 0]
fibo = mat_pow(mat, n-1)
print(fibo[0])

ㅎ 행렬 곱을 이용해서 피보나치 수를 구현했다.

분류되어있는 것을 무시하지 말자....

 

성공!