[Baekjoon]백준 피보나치 수 6(골드 2) - Python

문제설명

문제를 살펴보면 이전에 풀어보았던 피보나치수와 같다

다만, 주어지는 숫자가 커지고 그로 인하여 시간이 오래 걸리기 때문에 분할 정복 알고리즘을 사용하여

큰 숫자가 들어오더라도 빠른 속도로 연산을 하는 것이 목표이다

이 문제를 분할 정복 알고리즘으로 풀기위해 점화식을 먼저 찾아보았고, 그 덕분에 빠른 방법을 알게되었다

주어진 Fn, Fn-1, Fn-2를 활용하여 점화식을 만들수 있는데, 이를 행렬의 곱으로 표현할 수 있다

# 기본적인 피보나치 점화식:
#   | F(n)   | = | 1 1 | * | F(n-1) |
#   | F(n-1) |   | 1 0 |   | F(n-2) |

풀이코드에도 들어간 주석인데, 이 점화식을 활용함과 동시에 이전 문제에서 행렬의 제곱을 

분할정복을 사용하여 풀어보았기 때문에 이 코드를 거의 그대로 활용하여 작성하였다

이전 문제에서 달라진 것은 문제 조건과 곱셈을 수행할 때의 for문의 size가 아닌 2가 들어가야한다는 점이었다

def mul(a, b): # 행렬 곱셈 수행 
    res = [[0] * 2 for _ in range(2)] # 결과 저장 
    for i in range(2):
        for j in range(2):
            for k in range(2):
                res[i][j] += a[i][k] * b[k][j]
                res[i][j] %= MOD
    return res

def sol(x, n): # 행렬 거듭제곱 수행
    if n == 1:
        return x
    tmp = sol(x, n // 2)
    if n % 2: # n이 홀수인 경우
        return mul(mul(tmp, tmp), x)
    else: # n이 짝수인 경우 
        return mul(tmp, tmp)
    
MOD = 1000000007
num = int(input())
# 기본적인 피보나치 점화식:
#   | F(n)   | = | 1 1 | * | F(n-1) |
#   | F(n-1) |   | 1 0 |   | F(n-2) |
matrix = [[1, 1], [1, 0]]
result = sol(matrix, num)
print(result[0][1] % MOD)

초기 점화식 정보가 저장된 리스트를 함수 인자로 넣어주고, 계속하여 연산을 이어나가면 된다

이전 문제의 코드와 거의 동일하기 때문에 단계별로 풀어보기를 통해 이 문제를 푸는 분들은

점화식만 찾는다면 어렵지않게 해결가능한 문제이다