[BOJ] [Python] 1003번 : 피보나치 함수

 

처음에는 재귀함수를 이용해서 해결하려고 했다. 하지만 시간초과가 발생한다.

for문으로 바꾸니 해결됐다.

 

 

수기 작성

 

0의 개수와 1의 개수를 각각 계속 누적시켜서 더해준다.

 

num = int(input())

for _ in range(num):
    n = int(input())

    zero = [0] * (n + 1)
    one = [0] * (n + 1)

    for i in range(n + 1):

        if i == 0:
            zero[0] = 1

        elif i == 1:
            one[1] = 1

        else:
            zero[i] = zero[i - 2] + zero[i - 1]
            one[i] = one[i - 2] + one[i - 1]

    print(zero[i], one[i])

 

 

 

 

아래는 재귀함수를 이용한 풀이이다.

 

def fibo(n):
    if n == 0:
        li[0] += 1
        return 0

    elif n == 1:
        li[1] += 1
        return 1

    else:
        return fibo(n - 1) + fibo(n - 2)


num = int(input())
for _ in range(num):
    li = [0, 0]
    fibo(int(input()))
    print(li[0], li[1])