백준 [2749] 피보나치 수 3

백준 [2749] 피보나치 수 3

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 n번째 피보나치 수를 1,000,000으로 나눈 나머지를 출력한다.

 

 

풀이의 문제점

• 연산 횟수가 너무 많다.
• 보통 파이썬 1초 1천만번..? 1억번 가능
• 연산 횟수를 줄일 필요가 있다.

 

풀이의 핵심 1

피보나치 수열의 형태는 이러하다.

$$a_{n+2} \;= \; a_{n+1} \;+ \;a_{n}\\ a_{0} =0, \; a_{1} = 1$$

 

선형인 식이므로 이를 행렬형태로 바꾸면 이렇게 쓸 수 있다.

 

$$\begin{bmatrix} a_{n+2}\\ a_{n+1}\end{bmatrix}\;=\;\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \times \begin{bmatrix} a_{n+1}\\ a_{n}\end{bmatrix}$$

 

이렇게 쓸 경우 우리는 최종 항을 행렬의 연속된 곱의 형태로 쓸 수 있게 된다.

$$\begin{bmatrix} a_{n+2}\\ a_{n+1}\end{bmatrix}\;=\; \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \times \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \times ...\times \begin{bmatrix} a_{1}\\ a_{0}\end{bmatrix}\\ \begin{bmatrix} a_{n+2}\\ a_{n+1}\end{bmatrix}\;=\; \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n+1} \begin{bmatrix} a_{1}\\ a_{0}\end{bmatrix}$$

 

• 행렬의 n제곱을 어떻게 최적해서 만들 수 있느냐. 라는 문제로 변화됐다.

 

 

풀이의 핵심 2

$$3^{1000}$$

이 연산은 우리가 그냥 보기에 3을 1000번 계속해서 곱한다고 생각할 수 있다.

 

하지만 이제 다른 시각을 한번 보자.

$$15 = 1111_{(2)}\\ 3^{15}\; = \;3^{1111_{(2)}} = 3^{1000_{(2)}} \times 3^{100_{(2)}} \times 3^{10_{(2)}} \times 3^{1_{(2)}} \\$$

2진수로 쪼개면 이렇게 된다.

그런데 2진수로 나타냈을 때 각 자리수는 그 전 자리수의 제곱을 했을 때 나오는 결과이다.

 

$$3^{1000_{(2)}}\; = \; (3^{100_{(2)}})^{2}$$

 

$$3^{8} \; = \;3^{4} \times\;3 \times\;3 \times\;3 \times\;3 \\$$

아래의 연산을 컴퓨터로 한다면 총 4번의 반복이 필요하다.

 

하지만 2진수로 바꾼뒤 다음 연산만을 생각한다면 한번의 연산으로 이를 수행할 수 있다.

 

 

따라서 컴퓨터에서 지수연산을 할 때는,

1. 지수를 2진수로 바꾼다.
2. 각 자리에 해당하는 수가 몇개가 필요한지 판단한다.
3. 그 친구들만 곱한다.

로 정리할 수 있다.

 

그렇게 됐을 때 우리는 1000의 연산을 1111101000(2)로 바꾸어 10번 만에 값을 찾을 수 있다!

 

이걸 코드로 옮겨보자!

 

Answer

n = int(input())
mod = 1000000

def matmul(mat1,mat2):
    result = [[0,0],[0,0]]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                result[i][j] = (result[i][j] +  mat1[i][k] * mat2[k][j]) % mod
    return result

A0 = [[1], [0]]     # [a1, a0]
mul_op = [[1, 1], [1, 0]]
answer = [[1,0], [0, 1]]

n = n - 1

while(n > 0):  # 나눠서 몫이 0이 되는 경우까지 돌려라
    if (n % 2 == 1):
        answer = matmul(answer, mul_op)
    mul_op = matmul(mul_op, mul_op)
    n = n // 2

print(answer[0][0])   # 사실 A0 없어도 된다. answer[0][0] * 1  + answer[0][1] * 0이 답이니까

 

이 문제에서 답 형식

• 이미 인풋 자체가 너무 크기때문에 출력 형식을 Modulus 연산 수행 후 값을 답으로 채택했다.

 

$$a 의\; 나머지 + b의 \;나머지 = a+b의 \;나머지$$

 

지금 A0는 (1,0) 상태이기 때문에 모듈러스 연산이 필요없고

따라서 행렬의 각 요소를 모듈러스 연산을 수행한 이후의 값을 넣어주면

답 역시 모듈러스 연산을 수행한 결과값이 나오게 된다.