[백준] 11444번 피보나치 수 6 - PYTHON

백준 11444번

피보나치 수 6

분할정복

PYTHON

11444번 피보나치 수 6

시간 초과 코드

문제의 조건을 보면 n이 1,000,000,000,000,000,000보다 작은 수이다.

그렇기 때문에 아래와 같이 우리가 알고 있는 대로 해결하면 당연히 시간 초과가 발생한다.

---

소스 코드

문제를 해결하면서 이번 기회에 새로운 것을 배웠다.

매우 큰 피보나치 수의 값은 [[1,1],[1,0]] 모양의 2*2 행렬 거듭제곱을 통해서 구할 수 있다.

이 부분을 알게 되면 그 외의 부분은 행렬의 거듭제곱을 구하는 소스 코드이다.

matmul

matmul 함수는 이름 그대로 행렬의 곱 연산을 해주는 함수이다. 하지만 문제에서 1,000,000,007로 나눈 나머지를 구하도록 했기 때문에 원소를 전부 1,000,000,007로 나누어 주어야 한다.

power

power 함수는 거듭제곱을 구하는 함수이다.

짝수 승의 경우에는 반으로 나눈 값을 구해서 곱해주고
홀수 승의 경우에는 반으로 나눈 값을 구해서 곱해주고 1차 값을 곱해준다.

마지막으로 출력을 보면 함수의 거듭제곱 중 (0,1) 또는 (1,0)의 위치에 우리가 원하는 값이 있기 때문에 이 값을 출력한다.