백준 11444번 - 피보나치 수 6(C++)

문제

• 백준, 골드, https://www.acmicpc.net/problem/11444
• 풀이 날짜: 2025.3.17.
• 풀이 시간:  총 3시간 51분
• 사용 언어: C++

문제 해설

수학을 이용한 문제로, 공식을 모르면 풀 수 없다. 여기서는 도가뉴 항등식을 이용하여야 하며, 이를 활용하여 분할정복을 사용하여야 시간복잡도를 최적화할 수 있다.

내가 구했던 식 중 하나가 바로 도가뉴 항등식의 특수해로, $a_{2n}$에 대한 식까지는 어떻게든 유도했는데 그다음으로 넘어가는 데에 실패하여 다른 글을 찾아보게 되었다.

도가뉴 항등식은 피보나치 등식을 활용하여 변형한 것인데, 도가뉴 항등식은

$$ a_{m+n}=a_{m-1}a_n+a_m a_{n+1} $$

을 말한다(단, $a_n$은 피보나치 수열의 n번째 수).

도가뉴 항등식과 관련된 수식에 대한 글은 다음을 참조하였다.

https://blog.naver.com/lovingasal/221676326121

다만 이것만으로는 어떻게 할 수가 없고, 수 n의 크기가 최대 1,000,000,000,000,000,000이므로 logN 이하의 시간 복잡도를 갖는 알고리즘을 사용하여야 겨우 풀 수 있다.

잘 생각해보면, m 대신 여기에서 n을 대입하여, a_n을 이용하여 a_2n을 만들어낼 수만 있다면, 분할정복을 이용한 거듭제곱으로 큰 수를 logN의 시간으로 만들어낼 수 있을 것이다.

$$ \begin{align*} a_{2n}&=a_n(a_{n+1}+a_{n-1})\\ &=a_n(a_{n}+2a_{n-1}) \end{align*} $$

로 정리할 수 있고(피보나치 수열의 정의에 따라 $a_{n+1}=a_n+a_{n-1}$ 대입),

최종적으로 만들어야 하는 n이 홀수일 수도 있으므로, $a_{2n+1}$에 대하여

$$ a_{2n+1}=a_{2n}+a_{2n-1} $$

피보나치 수열의 정의에 따라 다음과 같이 계산하도록 한다.

이때 $a_{2n+1}$에서 $a_{2n-1}$을 요구하므로, 참조 시에 $a_{2n}$, $a_{2n-1}$을 함께 계산해야 한다.

$$ a_{2n-1}=(a_{n})^2-(a_{n-1})^2 $$

도가뉴 항등식의 응용으로 위와 같이 정의가 가능하다고 한다.

 

이를 이용하여, 수를 만들도록 해보자. 이때 방식은 분할정복을 이용한 거듭제곱을 만드는 것과 똑같다. 사용할 방식은 Bottom-up 방식으로 접근했다. 그로 인해 좀 복잡하게 보이긴 하는데, 방식은 단순하다.

 

(1) 상위 비트부터 검사하여 1일 경우 $a_{n+1}$을 구한다.

(2) 단, 첫 비트는 무조건 1이므로 무시한다.

(3) 한 비트를 검사했다면 $a_n$을 $a_{2n}$으로, $a_{n-1}$을 $a_{2n-1}$로 대체한다.

 

만약 n을 2진수로 표현했을 때, 100과 같은 꼴이라 해보자(n=4).

그러면 최초에는 $a_1=1$, $a_0=1$을 이용할 수 있다. k=1에서 k=n까지의 수를 완성해 보자.

이때, 참조할 땐 MSB에 해당하는 비트부터 확인한다. 즉, 왼쪽에서 오른쪽 순서로 검사한다.

 

1. 첫 비트(MSB)는 무조건 1이다. 예외적으로 첫 비트는 넘어가자.

- $a_1$을 $a_{2}$으로, $a_{0}$을 $a_{2n-1}=a_{1}$로 대체한다.

 

2. 상위 2번째 비트는 0이다.

- 두 번째 비트는 0이므로, $a_{2+1}$을 구할 필요가 없다.

- 이제 $a_2$를 $a_{4}$으로, $a_{1}$을 $a_{2n-1}=a_{3}$으로 대체한다.

 

3. 마지막 비트, 그러니까 LSB(가장 오른쪽 비트)는 0이다.

- 비트가 0이므로 $a_{4+1}$을 구할 필요가 없다.

 

4. 이제 모든 비트를 검사했으므로 과정을 종료한다.

 

이와 같은 방식으로 코드를 짜면 다음과 같이 정리할 수 있다.

#include <iostream>
#include <bitset> 
#define MOD 1000000007

using namespace std;

int main()
{
    long long n;
    long long bit = 1LL << 62;

    cin >> n;

    while ((bit & n) == 0)
    {
        bit >>= 1;
    }

    long long fib = 1LL, fib_prev = 0LL;

    while (bit > 1)
    {
        bit >>= 1;
        // 2 times
        long long double_fib = fib * (fib + 2 * fib_prev);
        long long double_fib_prev = fib * fib + fib_prev * fib_prev;
        double_fib %= MOD;
        double_fib_prev %= MOD;
        
        if (bit & n)
        {
            fib = (double_fib + double_fib_prev) % MOD;
            fib_prev = double_fib;
        }
        else
        {
            fib = double_fib;
            fib_prev = double_fib_prev;
        }
    }

    cout << fib << '\\n';

    return 0;
}