BOJ 7677 - Fibonacci (Python3)
분할 정복은 어떤 수의 거듭제곱만을 대상으로 하는 것이 아니다. 오히려 어떤 수의 거듭제곱보다는 행렬을 거듭제곱하는 것을 더욱 많이 볼 수 있다.
선형 점화식으로 주어진 수열일 경우 행렬을 거듭제곱함으로서 손 쉽게, 다이나믹 프로그래밍보다 훨씬 효율적으로, 매우 큰 n에 대하여 값을 구할 수 있다.
그럼 본격적으로 풀이에 돌입해 보자. 지문은 영어 한 줄, 해석 한 줄 번갈아서 표시된다.
문제
In the Fibonacci integer sequence, \(F_0 = 0, F_1 = 1\), and \(F_n = F_{n−1} + F_{n−2}\) for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
피보나치 수열은 다음 두 조건 \(F_0=0, F_1=1\)과, n이 2 이상일 때 \(F_n=F_{n-1}+F_{n-2}\)를 만족시키는 정수열이다. 예를 들어서 피보나치 수열의 처음 열 개 항은 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... 와 같다.
An alternative formula for the Fibonacci sequence is
피보나치 수열을 나타내는 다른 형태의 공식은 다음과 같다.
\[\begin{bmatrix} F_{ n+1 } & F_{ n } \\ F_{ n } & F_{ n-1 } \end{bmatrix}=\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n\]
Given an integer n, your goal is to compute the last 4 digits of \(F_n\).
당신의 목표는 정수 n이 주어졌을 때, \(F_n\)의 마지막 네 자리를 구하는 것이다.
입력
The input test file will contain multiple test cases. Each test case consists of a single line containing n (where 0 ≤ n ≤ 1,000,000,000). The end-of-file is denoted by a single line containing the number -1.
입력 파일은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 각 줄에 정수 n (0 ≤ n ≤ 1,000,000,000)이 주어진다. 입력의 마지막에는 숫자 -1이 들어온다.
예제 입력)
0
9
999999999
1000000000
-1
출력
For each test case, print the last four digits of \(F_n\). If the last four digits of \(F_n\) are all zeros, print ‘0’; otherwise, omit any leading zeros (i.e., print \(F_n\) mod 10000).
각각의 테스트 케이스에 대하여, \(F_n\)의 마지막 네 자리를 출력하라. 만약 \(F_n\)의 마지막 네 자리가 모두 0이라면, 0을 출력하라. 그렇지 않다면, 맨 앞자리의 0만을 제거하라(즉, \(F_n\)을 10000으로 나눈 나머지를 출력하라.).
예제 출력)
0
34
626
6875
내 코드
def mul(A,B):
ans = [[0,0],[0,0]]
for i in range(2):
for j in range(2):
eij = 0
for k in range(2):
eij += A[i][k]*B[k][j]
ans[i][j] = eij % 10000
return ans
Fib = [[1,1],[1,0]]
def power(b):
if b==1:
return Fib
X = power(b//2)
if b%2 == 0: return mul(X,X)
else: return mul(mul(X,X),Fib)
while True:
n = int(input())
if n == 0: print(0)
elif n == -1: break
else:
print(power(n)[1][0])
A를 \(\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\)라고 두면, 문제의 지문에 따라서 \(A^n\)의 (1,2) 혹은 (2,1) 성분이 바로 \(F_n\)이 된다.
여기서 n은 최악의 경우 10억. 당연히 일반적인 방법을 이용해 깡으로 계산하면 시간은 부족에 메모리는 터져 나갈 것이다.
비슷한 상황을 겪어 본 적 없는가? 그렇다. 18291번 문제.
분할 정복을 이용한 거듭제곱 계산을 아직 들어 본 적조차 없다면 18291번 문제의 사고방식을 확인하고 오자.
mul(A,B)는 두 행렬 A, B의 곱에서, 각 성분을 10000으로 나눈 나머지를 반환하는 함수이다. 사전에 이런 가공을 거치지 않는다면 메모리 초과라는 결과를 받을 것이다.
딱히 이 문제나 다른 분할 정복을 이용한 거듭제곱 문제가 아니더라도, 행렬의 곱셈 자체는 상당히 쓸 일이 많기 때문에 알아 두자. 기초 선형대수학은 몰라서 좋을 것이 하나 없다.
그리고 여기서의 Fib는 방금 말한 행렬 A. n제곱하여 (2,1)성분으로 \(F_n\)을 뱉어 줄 행렬이다.
마지막의 power(b)는? 분할 정복을 이용한 거듭제곱의 방법으로서 \(A^n\)을 뱉어내는 함수인 것이다.
필요한 성분만 뽑아서 검증하면 이 문제의 풀이는 끝.
이로서 7677번의 풀이를 마친다.
