[BAEKJOON] 백준 6571: 피보나치 수의 개수 (C#)

문제 링크

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

 

 

문제

피보나치 수의 정의는 다음과 같다.

• f1 := 1
• f2 := 2
• fn := fn-1 + fn-2 (n ≥ 3)

두 수 a와 b가 주어졌을 때, 구간 [a, b]에 포함되는 피보나치 수의 개수를 구하는 프로그램을 작성하시오.

 

 

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 음이 아닌 두 정수 a와 b로 이루어져 있다. 입력의 마지막 줄에는 0이 두 개 주어진다. (a ≤ b ≤ 10100) 두 수 a와 b는 불필요한 0으로 시작하지 않는다.

 

 

출력

각 테스트 케이스에 대해서, a ≤ fi ≤ b 인 피보나치 수 fi의 개수를 출력한다.

 

 

 

통과한 답안

using System.Numerics;

namespace _6571
{
    internal class Program
    {
        static List<BigInteger> Fibo = new List<BigInteger>();
        static void Main(string[] args)
        {
            Fibonacci();
            while (true)
            {
                string[] inputs = Console.ReadLine().Split(' ');
                BigInteger a = BigInteger.Parse(inputs[0]);
                BigInteger b = BigInteger.Parse(inputs[1]);

                if (a == 0 && b == 0)
                {
                    return;
                }

                int cnt = FindFibonacciCnt(a, b);
                Console.WriteLine(cnt);
            }
        }

        static void Fibonacci()
        {
            Fibo.Add(1);
            Fibo.Add(2);

            while (true)
            {
                BigInteger nextFibo = Fibo[Fibo.Count - 1] + Fibo[Fibo.Count - 2];
                if (nextFibo > BigInteger.Pow(10, 100))
                {
                    break;
                }
                Fibo.Add(nextFibo);
            }
        }

        static int FindFibonacciCnt(BigInteger a,  BigInteger b)
        {
            int start = 0;
            while (start < Fibo.Count && Fibo[start] < a)
            {
                start++;
            }

            int end = Fibo.Count - 1;
            while (end >= 0 && Fibo[end] > b)
            {
                end--;
            }

            if (start > end)
            {
                return 0;
            }

            return end - start + 1;
        }
    }
}

 

피보나치 수열 문제의 응용판으로 숫자 a와 b가 주어졌을 때,

a와 b 사이에 있는 피보나치 수의 개수를 찾는 문제이다.

 

이 문제는 특정 피보나치 수가 주어지거나 찾는게 아니라

주어진 수와 가까운 피보나치 수를 찾는 문제이며 여러 번의 연산을 해야되는 특징이 있다.

 

따라서 이를 해결하기 위해 처음에 피보나치 수들을 생성하는

Fibonacci() 메서드를 구현하여 작동하게 만들었다.

 

이후에 FindFibonacciCnt() 메서드를 이용하여 

주어지는 수 a와 b 사이에 있는 피보나치 수를 찾도록 구현하였다.