백준 11444번 : 피보나치 수 6[C#]

비네의 법칙에 거듭제곱 분할정복 + 나머지연산으로 해보려다가 루트때문에 오차가 커지는바람에 시원하게 틀리고 돌아왔습니다.

 

이 문제는 피보나치 수열의 규칙성을 행렬의 제곱형태의 식으로 생각해낼 수 있는지를 보는 문제입니다.

 

정답부터 말씀드리면 피보나치 수열을 행렬로 바꾸면

 

이 식이 도출되고, 그 후에 코드로 작성하는 방법은 행렬 제곱 문제와 같은 방식을 사용합니다.

 

using System;
using System.Numerics;

class Program
{
    static long P = 1000000007;

    static void Main()
    {
        long n = long.Parse(Console.ReadLine());

        long[,] power = Power(n - 1);

        long ans = power[0, 0] % P;

        Console.Write(ans);
    }

    static long[,] Power(long time)
    {
        long[,] res = { { 1, 0 }, { 0, 1 } };
        long[,] Unit = { { 1, 1 }, { 1, 0 } };

        while (time != 0)
        {
            long[,] temp = new long[2, 2]; // 임시저장 행렬

            if (time % 2 == 1) // 홀수 인 경우
            {
                for (int r = 0; r < 2; r++)
                {
                    for (int c = 0; c < 2; c++)
                    {
                        for (int i = 0; i < 2; i++)
                        {
                            temp[r, c] += (res[r, i] * Unit[i, c]) % P;
                        }
                    }
                }

                res = temp;
            }

            temp = new long[2, 2]; // 임시저장 행렬

            for (int r = 0; r < 2; r++)
            {
                for (int c = 0; c < 2; c++)
                {
                    for (int i = 0; i < 2; i++)
                    {
                        temp[r, c] += (Unit[r, i] * Unit[i, c]) % P;
                    }
                }
            }
            Unit = temp;

            time /= 2;
        }

        return res;
    }
}

 

 

* 느낌점

피보나치 수를 행렬로 나타내려면 피보나치 수를 여러 개의 F1과 F0의 합으로 바라보는 시선이 필요했습니다.

다른 알고리즘 문제를 풀 때에도 비슷한 패턴에서 행렬을 떠올려보면 좋을 것 같아요.