[알고리즘 문제 풀기] 피보나치 수 6(11444)

1. 문제 풀이 아이디어

• 도카뉴 수열(Docagne Sequence)을 활용하여 분할 정복으로 문제를 해결할 수 있다.

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());
    sw.WriteLine(Docagne(n));

    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(l) 함수는 재귀적으로 값을 계산하며, 메모이제이션을 활용하여 중복 연산을 방지한다.

• l == 0일 때 0, l == 1 또는 l == 2일 때 1을 반환한다.

• l이 이미 계산된 경우 사전에 저장된 값을 반환한다.

• l을 a와 b로 나누어 점화식을 적용하고, 결과를 1000000007로 나눈 나머지를 저장한다.

• Docagne(n)의 결과를 출력한여 문제를 해결한다.