[BAEKJOON] 백준 9711: 피보나치 (C#)

문제 링크

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

 

 

문제

피보나치 수열은 아래와 같이 표현된다.

1, 1, 2, 3, 5, 8, 13, 21, 34, ...

각 숫자는 앞의 두 숫자의 합으로 나타내는 것을 알 수 있다.

P와 Q 그리고 n이 주어질 때, P번째 피보나치 숫자를 Q로 나눈 나머지를 구하여라. 

 

 

입력

첫 번째 라인에는 정수 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 정수 P와 Q가 주어진다.

 

 

출력

각 테스트 케이스마다 "Case #x: M" 형식으로 출력한다.

x는 테스트 케이스 번호(1부터 시작), M은 P번째 피보나치 숫자를 Q로 나눈 나머지이다.

 

 

제한

• 1 ≤ P ≤ 10,000
• 1 ≤ Q ≤ 2,000,000,000

 

 

 

통과한 답안

using System.Numerics;
using System.Text;

namespace _9711
{
    internal class Program
    {
        static List<BigInteger> Fibo = new List<BigInteger>();
        static void Main(string[] args)
        {
            int T = int.Parse(Console.ReadLine());
            StringBuilder sb = new StringBuilder();

            Fibonacci();

            for (int i = 0; i < T; i++)
            {
                string[] inputs = Console.ReadLine().Split(' ');
                int P = int.Parse(inputs[0]) - 1;
                long Q = long.Parse(inputs[1]);
                BigInteger answer = Fibo[P] % Q;

                sb.AppendLine($"Case #{i + 1}: {answer}");
            }

            Console.WriteLine(sb.ToString());
        }

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

            for (int i = 2; i < 10000; i++)
            {
                Fibo.Add(Fibo[i - 1] + Fibo[i - 2]);
            }
        }
    }
}

 

피보나치 수에 대해서 P번째 피보나치 수를 Q로 나눈 나머지를 찾는 문제이다.

 

이 문제의 경우 매번 새롭게 피보나치 수를 찾거나 Q로 나눈 나머지를 저장하는 방식은

T의 범위가 크다면 시간 초과가 발생할 것으로 판단하여

 

초기에 최대 범위(10000번째 피보나치 수)로 피보나치 수를 계산한 뒤에

필요한 피보나치 수를 불러와서 Q로 나눈 나머지를 구하도록 구현하였다.

또, T의 범위로 인하여 Console.WriteLine() 함수를 여러번 호출하는 경우에도

시간 초과가 발생할 수 있으므로 StringBuilder를 활용하였다.

 

BigO 시간 복잡도는 피보나치 수를 초기화하는 곳에서 O(10000)이고

이후에 T번의 연산을 반복하는데, 각 연산마다 O(1)을 반복하므로

결과적으로 O(T + 10000)이 되며, BigO 시간 복잡도는 큰 값만 표기하므로

BigO(T)라고 표기할 수 있다.