[백준] 1003 - 피보나치 함수

1. 문제

1003번: 피보나치 함수

2. 개요

재귀로 피보나치 수를 구하는 함수 Fibonacci(N)이 호출되었을 때,

Fibonacci(0) 과 Fibonacci(1)이 각각 몇 번 호출되는지 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

Fibonacci(0)과 Fibonacci(1)의 호출 횟수 역시 피보나치 수의 규칙을 따른다

즉 Fibonacci(N)의 Fibonacci(0)은 Fibonacci(N-2)와 Fibonacci(N-1)의 Fibonacci(0) 호출 횟수를 더한 값과 같고 Fibonacci(1)은 Fibonacci(N-2)와 Fibonacci(N-1)의 Fibonacci(1) 호출 횟수를 더한 값과 같다. 이를 이용해 dp테이블을 완성하고 답을 출력한다.

3-2. Python

import sys

dp = [[0, 0] for i in range(41)]
dp[0] = [1, 0]
dp[1] = [0, 1]
dp[2] = [1, 1]

for i in range(3, 41):
    dp[i][0], dp[i][1] = dp[i-2][0] + dp[i-1][0], dp[i-2][1] + dp[i-1][1]

T = int(sys.stdin.readline())

for t in range(T):
    N = int(sys.stdin.readline())

    print(*dp[N])

3-3. C#

namespace boj_1003
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int[,] dp = new int[41, 2];

            dp[0, 0] = 1;
            dp[1, 1] = 1;
            dp[2, 0] = 1;
            dp[2, 1] = 1;

            for (int i = 3; i < 41; i++)
            {
                dp[i, 0] = dp[i - 2, 0] + dp[i - 1, 0];
                dp[i, 1] = dp[i - 2, 1] + dp[i - 1, 1];
            }

            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            int T = int.Parse(sr.ReadLine());

            for (int t = 0; t < T; t++)
            {
                int N = int.Parse(sr.ReadLine());
                sw.WriteLine($"{dp[N, 0]} {dp[N, 1]}");
            }

            sw.Close();
        }
    }
}