2022.02.06 [백준] C# 피보나치 함수

 

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

1003번: 피보나치 함수

---

풀이

처음 재귀함수를 이용해서 문제를 해결하려 했지만 시간초과가 발생했다. 그래서 구글링 중, 재귀함수가 아닌 배열을 이용해서 문제를 해결할 수 있다고 알게 되었다.

문제에서 n의 범위가 40이하의 자연수여서 이차원 배열의 범위를 int[41,2]로 설정했고, for문을 이용하여 모든 범위의 수에서 0, 1이 몇 개씩 들어가는지 배열에 넣었다. 그리고 테스트 케이스에 맞게 바로 출력했다.

using System;
using System.Text;
using System.IO;
 
class Program
{
    
    
    static void Main()
    {
        StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
        StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));
        StringBuilder sb = new StringBuilder();
        int n = int.Parse(sr.ReadLine());
        int[,] fibo = new int[41, 2];
        fibo[0, 0] = 1;
        fibo[1, 1] = 1;
        for (int i = 2; i < 41; i++)
        {
            fibo[i, 0] = fibo[i - 1, 0] + fibo[i - 2, 0];
            fibo[i, 1] = fibo[i - 1, 1] + fibo[i - 2, 1];
        }
        for(int i = 0; i < n; i++)
        {
            int a = int.Parse(sr.ReadLine());
            sb.Append($"{fibo[a, 0]} {fibo[a, 1]}" + "\n");
        }
        sw.WriteLine(sb.ToString());
        sr.Close();
        sw.Close();
    } 
}