1003 - 피보나치 함수

일단 경우의 수를 나열해본다.

 

fibonacci(0) = call fibonacci(0) = 1, 0

fibonacci(1) = call fibonacci(1) = 0, 1

fibonacci(2) = call fibonacci(2) = call fibonacci(1), call fibonacci(0) = 1, 1

fibonacci(3) = call fibonacci(3) = call fibonacci(2), call fibonacci(1) = 1, 2

fibonacci(4) = call fibonacci(4) = call fibonacci(3), call fibonacci(2) = 2, 3

fibonacci(5) = call fibonacci(5) = call fibonacci(4), call fibonacci(3) = 3, 5

 

위의 경우를 살펴보면 결과 값은 입력되는 숫자가 n이면, 피보나치 수열의 n번째 하고 n-1번째이다. 입력이 0일때만 특수한 경우임으로 if 문으로 출력하면 된다.

 

 

First lets try writing down the first few outputs

 

fibonacci(0) = call fibonacci(0) = 1, 0

fibonacci(1) = call fibonacci(1) = 0, 1

fibonacci(2) = call fibonacci(2) = call fibonacci(1), call fibonacci(0) = 1, 1

fibonacci(3) = call fibonacci(3) = call fibonacci(2), call fibonacci(1) = 1, 2

fibonacci(4) = call fibonacci(4) = call fibonacci(3), call fibonacci(2) = 2, 3

fibonacci(5) = call fibonacci(5) = call fibonacci(4), call fibonacci(3) = 3, 5

 

As shown above, if the input is the number ‘n’, the output is a list with the ‘n’th Fibonacci number and ‘n-1’th Fibonacci number. The only exception is using 0 as the input number. This can be solved using a single ‘if’ statement.

 

Python Code:

import sys


# List to save fibo lists
g_fibo_list = [0, 1]


def get_fibo_num(input_num) -> int:
    """
        Get fibonacci number from global list if possible, else calculate till the index wanted
        Arguments:
            input_num: the index of fibonacci list wanted
        Returns:
            The fibonacci number for the index inputted
    """

    # While the fibonacci list doesn't have the index
    while input_num >= len(g_fibo_list):
        # Add another list to the end of the global list using the last two lists
        g_fibo_list.append(g_fibo_list[-1] + g_fibo_list[-2])

        # Log change
        print(f"{g_fibo_list[-1]} added to list")

    # Return the fibonacci list from the global list
    return g_fibo_list[input_num]


def main() -> None:
    # Number of test cases
    case_num = int(sys.stdin.readline().rstrip())

    # Loop for each test case
    for _ in range(case_num):
        # Get input number
        input_num = int(sys.stdin.readline().rstrip())

        # Check input_num
        print(f"input_num: {input_num}")

        # Check list for input num as index
        output_list = [get_fibo_num(input_num - 1), get_fibo_num(input_num)]

        # Check exception
        if input_num == 0:
            output_list = [1, 0]

        # Check output_list
        print(f"output_num: {output_list}")

        # Print output list
        print(' '.join(map(str, output_list)))
        
    return


if __name__ == '__main__':
    main()