[BAEKJOON] 백준 14495: 피보나치 비스무리한 수열 (C#)

문제 링크

https://www.acmicpc.net/problem/14495

 

 

문제

피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. f(1) = f(2) = f(3) = 1이며 피보나치 비스무리한 수열을 나열하면 다음과 같다.

1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ...

자연수 n을 입력받아 n번째 피보나치 비스무리한 수열을 구해보자!

 

 

입력

자연수 n(1 ≤ n ≤ 116)이 주어진다.

 

 

출력

n번째 피보나치 비스무리한 수를 출력한다.

 

 

 

통과한 답안

using System.Numerics;

namespace _14495
{
    internal class Program
    {
        static Dictionary<int, BigInteger> Fibo = new Dictionary<int, BigInteger>();
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            Console.WriteLine(fibonacci(n).ToString());
        }

        static BigInteger fibonacci(int n)
        {
            Fibo[1] = 1;
            Fibo[2] = 1;
            Fibo[3] = 1;
            int cnt = 4;

            while (!Fibo.ContainsKey(n))
            {
                Fibo[cnt] = Fibo[cnt - 1] + Fibo[cnt - 3];
                cnt++;
            }

            return Fibo[n];
        }
    }
}

 

피보나치 수열과 비슷하게 구현하였는데,

조건이 f(n) = f(n-1) + f(n-3) 이므로,

이를 반영하여 Dictionary에 저장되도록 구현하였다.