[Python] BOJ/백준 1003번 피보나치 함수

[문제]

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

1003번: 피보나치 함수

 

[풀이]

이 문제는 피보나치 값이 아닌, 특정 값의 피보나치를 구하기 위해 호출되는

fibonaaci(0)과 fibonacci(1)의 호출 횟수를 구하는 것이다.

 

피보나치 문제는 문제 답 저장 후 해당 부분이 필요한 경우 저장된 결과를 사용하는 동적 계획법

으로 풀었다.

 

fibonacci(n)을 구하기 위해서는 fibonacci(n-1)와 fibonacci(n-2)을 더해야 하기 때문에

fibonacci(n)을 호출할 경우 실행되는 fibonacci(0)과 fibonacci(1)은

'fibonacci(n-1)의 0과 1 호출 횟수' + 'fibonacci(n-2)의 0과 1 호출 횟수'와 일치한다

 

0과 1이 호출되는 값을 저장할 리스트를 각각 만들어준 후 이미 알고있는 값은 미리 배열에 선언해준다.

리스트 zero의 경우 0일 때 0이 1번 출력, 1일 때 0번 출력, 2일 때 1번 출력되기 때문에 [1, 0, 1]로 초기해주었다.

one도 위의 방법과 마찬가지로 초기화해준다.

 

구하려는 숫자가 이전에 구했던 숫자들보다 큰 숫자인 경우 리스트에 값을 갱신해준다.

 

[코드]

import sys

def fibonacci(num):
    length = len(zero)
    if num >= length:
        for i in range(length, num + 1):
            zero.append(zero[i - 1] + zero[i - 2])
            one.append(one[i - 1] + one[i - 2])
    print('{} {}'.format(zero[num], one[num]))

if __name__ == '__main__':
    input = sys.stdin.readline

    zero = [1, 0, 1]
    one = [0, 1, 1]

    for _ in range(int(input().rstrip())):
        fibonacci(int(input().rstrip()))