[Python 파이썬]백준 2749번 피보나치 수 3 풀이

문제

여타 다를 것없는 피보나치 수를 찾는 문제인데...
입력이 1,000,000,000,000,000,000까지다.
100경..

DP로 풀면 100경 번 연산.. 불가능하다..

풀이

어떻게 풀어야할지 고민하다가 보통 입력이 이렇게 크면 O(logn)으로 해결 가능해야하니까 분할정복 밖엔 답이 없나라는 생각이 든다.

음.. 근데 피보나치를 어떻게 분할정복으로 풀지...
보통 분할정복하면 배열을 분할하거나.. 거듭제곱같은 거 분할해서 계산하거나... 그런데 계속 증가하는 수열인 피보나치를 분할정복으로..?

는 예전에 경제 수학 시간에 행렬로 다룬 적이 있어서 그 방법을 이용했다.

이런 방법으로 피보나치를 행렬로 바꿀 수 있다.

---

이를 일반적인 형태로 바꾸면, n >= 2 에서 아래 식이 성립한다.

---

이제 행렬부분 곱셈만 코드로 구현하고, 일반적인 n제곱 분할정복하는 것처럼 만들어주면 되겠다..!

코드

---

def matrix_multiply(matrix1, matrix2):
    matrix1_matrix2 = [
        [(matrix1[0][0] * matrix2[0][0] + matrix1[0][1] * matrix2[1][0]) % 1000000,
         (matrix1[0][0] * matrix2[0][1] + matrix1[0][1] * matrix2[1][1]) % 1000000],
        [(matrix1[1][0] * matrix2[0][0] + matrix1[1][1] * matrix2[1][0]) % 1000000,
         (matrix1[1][0] * matrix2[0][1] + matrix1[1][1] * matrix2[1][1]) % 1000000]
    ]
    return matrix1_matrix2

def fib(number):
    if number <= 1:
        return [[1, 1], [1, 0]]

    if number % 2 == 0:
        new = fib(number // 2)
        return matrix_multiply(new, new)
    else:
        new = fib((number - 1) // 2)
        return matrix_multiply(matrix_multiply(new, new), fib(1))

n = int(input())
if n <= 2:
    result = 1
else:
    a = fib(n-2)
    result = (a[0][0] + a[0][1]) % 1000000

print(result)

---

대충 이런 느낌..!

아 참고로 분할할 때, Integer division (//) 안쓰고 그냥 / 쓰면 틀린다. 컴퓨터 특성 상(?) 큰 수를 나눴을 때 오차가 생기기 때문에..!

(이거 때문에 한참 고민했네..)