[알고리즘 문제 풀기] 피보나치 수의 제곱의 합(11440)

1. 문제 풀이 아이디어

• 도카뉴 수열(Docagne Sequence)을 활용하여 피보나치 수를 구한 후, n까지의 제곱의 합이 n번째 수와 (n+1)번째 수의 곱과 같다는 성질을 이용하여 문제를 해결한다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    Dictionary<long, long> dic = new Dictionary<long, long>();
    long n = long.Parse(sr.ReadLine());
    long n1 = Docagne(n);
    long n2 = Docagne(n+1);
    sw.WriteLine(n1 * n2 % 1000000007);

    long Docagne(long l)
    {
        if (l == 0) return 0;
        if (l == 1 || l == 2) return 1;
        if (dic.ContainsKey(l)) return dic[l];
        long a = l / 2 + l % 2;
        long b = l / 2;
        long result = (Docagne(a - 1) * Docagne(b) + Docagne(a) * Docagne(b + 1)) % 1000000007;
        dic.Add(l, result);
        return result;
    }
}

3. 정리

• Docagne(long l)을 구현하여 n번째와 (n+1)번째 피보나치 수를 구한다.

• 두 수를 곱한 결과를 1000000007로 나누어 문제를 해결한다.