boj-11444 피보나치 수 6

https://www.acmicpc.net/problem/11444

문제 소개

n이 주어졌을 때, n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다.

n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다.

문제 풀이

도가뉴 항등식으로 풀이하였다. 도가뉴 항등식은 아래와 같다.

\[F_{m+n}=F_{m-1}F_n+F_mF_{n+1}\]

m과 n에 각각 n을 대입하면 아래와 같다.

\[F_{n+n}=F_{n-1}F_n+F_nF_{n+1}\\=F_n(F_{n-1}+F_{n+1})\\=F_n(F_{n-1}+F_{n-1}+F_n)\\=F_n(F_n+2*F_{n-1})\]

또한 m과 n에 각각 n + 1과 n을 대입하면 아래와 같다.

\[F_{n+1+n}=F_nF_n+F_{n+1}F_{n+1}\\={F_n}^2+{F_{n+1}}^2\]

위에서 얻은 두 식을 n이 짝수인 경우와 홀수인 경우에 각각 적용하여 문제를 분할 정복 방식으로 풀어나갈 수 있다.

map memo에는 메모이제이션으로 한 번 연산하였던 피보나치 수의 값을 저장한다. n에 대한 연산 전에 초기값으로 0번째 피보나치 수인 0과 1번째 피보나치 수인 1을 추가해 놓는다.

함수 fib()는 해당 순서의 피보나치 수를 구하는 함수이다. 인자로 들어온 n이 memo에 없다면 짝수인지 홀수인지 판별 후 위 두 식에 따라 더 작은 문제로 쪼개어 재귀적으로 연산한다.

중간 계산값이 자료형의 표현 범위를 초과하지 않게 미리 1000000007으로 선언해 둔 m으로 모듈러 연산도 해 준다.

코드

#include <iostream>
#include <map>

int m = 1000000007;
std::map<int, int> memo;

// fib(2 * n) = fib(n) * (fib(n) + 2 * fib(n - 1))
// fib(2 * n + 1) = fib(n) ^ 2 + fib(n + 1) ^ 2

long long fib(long long n) {
	if (memo.find(n) == memo.end()) {
        // n이 홀수라면
		if (n & 1) {
			long long t1 = fib(n / 2);
			long long t2 = fib(n / 2 + 1);
			memo[n] = ((t1 * t1) % m + (t2 * t2) % m) % m;  // 중간에 모듈러 연산을 해 주자
		}
        // n이 짝수라면
		else {
			long long t1 = fib(n / 2);
			long long t2 = fib(n / 2 - 1);
			memo[n] = (t1 * (t1 + 2 * t2)) % m;
		}
	}
	return memo[n];
}

int main() {
	using namespace std;
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

    // 0번째와 1번째 피보나치 수 추가
	memo.insert({ 0, 0 });
	memo.insert({ 1, 1 });

	long long n;
	cin >> n;

	cout << fib(n) << '\n';

	return 0;
}