[백준/파이썬] 1003번 : 피보나치 함수

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

1003번: 피보나치 함수

import sys

t = int(sys.stdin.readline())
for _ in range(t):
    a = int(sys.stdin.readline())
    if a == 0:
        print(1, 0)
        continue
    elif a == 1:
        print(0, 1)
        continue
    arr = [[0] * 2 for _ in range(a + 1)]
    arr[0] = [1, 0]
    arr[1] = [0, 1]
    for i in range(2, a + 1):
        arr[i] = [arr[i - 2][0] + arr[i - 1][0], arr[i - 2][1] + arr[i - 1][1]]
    print(arr[a][0], arr[a][1])

 

 

기본재귀함수를 사용하여 0과 1이 호출될 때마다 개수를 세어 출력하면 시간초과가 떠 다른 풀이를 생각해 보았다.

먼저 입력받은 값 a 가 0 또는 1 일 경우에는 출력을 해준다.

1보다 클 경우에는 arr 2차원 리스트를 선언하고 반복문을 통해 0이 나오는 횟수와 1이 나오는 횟수를 피보나치 수로 더해준다.

 

f(2) = f(1) + f(0) 이 식을 출력 횟수로 보면

[1,1] = [0,1]+[1,0] 으로 볼 수 있다.