[BAEKJOON] 백준 1788: 피보나치 수의 확장 (C#)

문제 링크

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

 

 

문제

수학에서, 피보나치 수는 위의 점화식과 같이 귀납적으로 정의되는 수열이다. 위의 식에서도 알 수 있듯이, 피보나치 수 F(n)은 0 이상의 n에 대해서만 정의된다.

하지만 피보나치 수 F(n)을 n이 음수인 경우로도 확장시킬 수 있다. 위의 식에서 n > 1인 경우에만 성립하는 F(n) = F(n-1) + F(n-2)를 n ≤ 1일 때도 성립되도록 정의하는 것이다. 예를 들어 n = 1일 때 F(1) = F(0) + F(-1)이 성립되어야 하므로, F(-1)은 1이 되어야 한다.

n이 주어졌을 때, 피보나치 수 F(n)을 구하는 프로그램을 작성하시오. n은 음수로 주어질 수도 있다.

 

 

입력

첫째 줄에 n이 주어진다. n은 절댓값이 1,000,000을 넘지 않는 정수이다.

 

 

출력

첫째 줄에 F(n)이 양수이면 1, 0이면 0, 음수이면 -1을 출력한다. 둘째 줄에는 F(n)의 절댓값을 출력한다. 이 수가 충분히 커질 수 있으므로, 절댓값을 1,000,000,000으로 나눈 나머지를 출력한다.

 

 

 

통과한 답안

namespace _1788
{
    internal class Program
    {
        static Dictionary<int, long> positiveFibo = new Dictionary<int, long>();
        static Dictionary<int, long> negativeFibo = new Dictionary<int, long>();
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            long answer = 0;
            if (n > 0)
            {
                answer = posiFibo(n);
                Console.WriteLine(1);
                Console.WriteLine(answer);
            }
            else if (n == 0)
            {
                Console.WriteLine(0);
                Console.WriteLine(0);
            }
            else
            {
                answer = negaFibo(n);
                Console.WriteLine(answer > 0 ? 1 : -1);
                Console.WriteLine(Math.Abs(answer));
            }
        }

        static long posiFibo(int n)
        {
            positiveFibo[0] = 0;
            positiveFibo[1] = 1;
            int cnt = 2;

            while (!positiveFibo.ContainsKey(n))
            {
                positiveFibo[cnt] = (positiveFibo[cnt - 1] + positiveFibo[cnt - 2]) % 1000000000;
                cnt++;
            }

            return positiveFibo[n];
        }

        static long negaFibo(int n)
        {
            negativeFibo[0] = 0;
            negativeFibo[1] = 1;
            int cnt = -1;

            while (!negativeFibo.ContainsKey(n))
            {
                negativeFibo[cnt] = (negativeFibo[cnt + 2] - negativeFibo[cnt + 1])% 1000000000;
                cnt--;
            }

            return negativeFibo[n];
        }
    }
}

 

기존의 피보나치 수열에서 파생되어 n을 음수로 확장한 피보나치 수열이다.

코드를 좀 더 명확하게 구분하기 위해

양수의 피보나치 수열과 음수의 피보나치 수열을 나눠서 구현하였는데,

양수의 피보나치 수열은 일반적인 피보나치 수열을 그대로 채용하였다.

 

음수의 피보나치 수열은 같은 방식으로는 구현할 수 없으므로

F(n) = F(n - 1) + F(n - 2) 를 F(n - 2) = F(n) - F(n - 1)을 이용하여

F(n) = F(n + 2) - F(n + 1)로 구현하였다.

 

이후에 입력되는 수에 따라서 해당하는 피보나치 함수를 작동시키고,

음수의 경우에는 -1을 출력하고 절대값을 출력하도록 구현하였다.

 

 

단, 이렇게 구분하지 않고 한 번에 코드를 구현할 수 있는데,

아래와 같은 방식으로 코드를 작성할 수도 있다.

namespace _1788_2_
{
    internal class Program
    {
        static Dictionary<int, long> Fibo = new Dictionary<int, long>();
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            long answer = Fibonacci(n);
            Console.WriteLine(answer == 0 ? 0 : (answer > 0 ? 1 : -1));
            Console.WriteLine(Math.Abs(answer));
        }

        static long Fibonacci(int n)
        {
            Fibo[0] = 0;
            Fibo[1] = 1;
            Fibo[-1] = 1;
            
            while (!Fibo.ContainsKey(n))
            {
                if (n > 1)
                {
                    Fibo[n] = (Fibonacci(n - 1) + Fibonacci(n - 2)) % 1000000000;
                }
                else
                {
                    Fibo[n] = (Fibonacci(n + 2) - Fibonacci(n + 1)) % 1000000000;
                }
            }

            return Fibo[n];
        }
    }
}

 

이 코드의 경우에는 양수와 음수 모두 하나의 Dictionary에서 관리하며,

입력되는 n 값에 따라서 해당하는 값까지 필요한 과정들을 저장하며 나아가게 구현하였다.

 

다만 위의 코드가 좀 더 명확하게 이해할 수 있으며,

 

채점에서도 훨씬 효율적인 코드라고 판단할 수 있는 결과를 얻었다.