문제
N번째 피보나치 수를 1,000,000,007로 나눈 나머지를 구하는 문제이다. N이 최대 1,000,000,000,000,000,000(10^18)이므로 단순 반복으로는 불가능하다.
입력
첫째 줄에 N(1 ≤ N ≤ 10^18)이 주어진다.
출력
N번째 피보나치 수를 1,000,000,007로 나눈 나머지를 출력한다.
예제
| 입력 | 출력 |
|---|---|
1000 | 517691607 |
풀이
피보나치 수열의 행렬 거듭제곱 성질을 활용한다. 피보나치 점화식은 2x2 행렬로 표현할 수 있다.
행렬 [[1,1],[1,0]]의 N-1제곱을 구하면 [0][0] 원소가 F(N)이 된다.
- 기저 행렬
A = [[1,1],[1,0]]을 정의한다. - 분할 정복으로
pow(A, N-1)을 계산한다. 지수를 절반으로 줄이며 재귀 호출하고, 홀수이면 원본 행렬을 추가로 곱한다. - 행렬 곱셈 시 각 원소를 MOD(10^9 + 7)로 나눈 나머지를 취한다.
- 결과 행렬의
[0][0]원소가 F(N)이다.
핵심 아이디어: 피보나치의 행렬 표현 [[F(n+1), F(n)], [F(n), F(n-1)]] = [[1,1],[1,0]]^n을 이용한다. 분할 정복으로 행렬 거듭제곱을 O(log N)에 계산하면 N = 10^18도 처리 가능하다.
코드
package com.ssafy.an.day149;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Day140BOJ11444피보나치행렬곱 { // 11444 피보나치 수 6 분할정복 행렬 곱셈
final static long MOD = 1000000007;
public static long[][] origin = { { 1, 1 }, { 1, 0 } };
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long[][] A = { { 1, 1 }, { 1, 0 } };
long N = Long.parseLong(br.readLine());
System.out.println(pow(A, N - 1)[0][0]);
br.close();
}
public static long[][] pow(long[][] A, long exp) {
if (exp == 1 || exp == 0)
return A;
long[][] ret = pow(A, exp / 2);
ret = multiply(ret, ret);
if (exp % 2 == 1L)
ret = multiply(ret, origin);
return ret;
}
public static long[][] multiply(long[][] o1, long[][] o2) {
long[][] ret = new long[2][2];
ret[0][0] = ((o1[0][0] * o2[0][0]) + (o1[0][1] * o2[1][0])) % MOD;
ret[0][1] = ((o1[0][0] * o2[0][1]) + (o1[0][1] * o2[1][1])) % MOD;
ret[1][0] = ((o1[1][0] * o2[0][0]) + (o1[1][1] * o2[1][0])) % MOD;
ret[1][1] = ((o1[1][0] * o2[0][1]) + (o1[1][1] * o2[1][1])) % MOD;
return ret;
}
}복잡도
- 시간: O(log N) — 행렬 곱셈은 2x2이므로 상수 시간, 지수를 log N번 절반으로 줄임
- 공간: O(log N) — 재귀 스택 깊이