11444 피보나치 수 6

코딩테스트 : 11444 피보나치 수 6

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다.

using System.Text;

public class BackJoon
{
    private static Dictionary<long, long> memo = new() { { 0, 0 }, {1,1} };
    private const long MOD = 1000000007;
    public static void Main()
    {
        long n = long.Parse(Console.ReadLine());

        //피보나치 수열의 규칙 F(n) = F(n-1) + F(n - 2) ;
        //배열선언은 좀 그렇고, 나눗셈 log n 으로 해야 함
        //짝수일 경우에는 ? 홀수일 경우에는 ?

        // 공식 : 찾아봄

        Console.WriteLine(Fibonacci(n));
    }

    public static long Fibonacci(long n)
    {
        if (memo.ContainsKey(n)) return memo[n];

        long result;
        if (n % 2 == 0)
        {
            long a = Fibonacci(n / 2 - 1);
            long b = Fibonacci(n / 2);
            result = ((2 * a + b) % MOD * b) % MOD;
        }
        else
        {
            long a = Fibonacci(n / 2);
            long b = Fibonacci(n / 2 + 1);
            result = (a * a % MOD + b * b % MOD) % MOD;
        }
        
        return memo[n] = result;
    }
 
}

 

사고의 흐름을 좀 정리해보자면

 

1. 피보나치.. ? DP로 하면 안되는건가  ? 배열에 저장하면서 ? 
흠 입력이 1,000,000,000,000,000,000개면 절대 안되겠구나 ! 

2. 지금 파트가 분할 정복이니까 절반인 것으로 나눌 수 있나 ?

3. 공식을 모르니까 찾아봐야지... 

하고 풀었다. 

 

유도해 보려고 했으나 실패. 

 

이런 사고 흐름을 유지해야 할 것 같다.

애초에 이 문제도 증명을 찾아보니 행렬곱으로 피보나치 수열의 F(2N) 를 구하는 공식을 유도할 수 있었다.

다만, 나는 지금 '수학'을 공부하는 것이 아니기 때문에 이런 방식으로 공식은 찾아보면서 하는 것이 맞다고 생각한다.