[알고리즘 문제 풀기] 홀수번째 피보나치 수의 합(11442)

1. 문제 풀이 아이디어

• 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());
    sw.WriteLine(Docagne(n % 2 == 0 ? n : n + 1));

    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(n)은 도카뉴 수열의 n번째 값을 구한다.

• n이 홀수이면 짝수로 변환해 계산하며, 각 계산 결과는 딕셔너리에 저장한다.

• Docagne(n) = Docagne(a - 1) * Docagne(b) + Docagne(a) * Docagne(b + 1) 공식을 통해 값을 구한다.