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

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

1003번: 피보나치 함수

Problem

• N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

조건

• 첫째 줄에 테스트 케이스의 개수 T가 주어진다.
• 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

SOL

 

피보나치 함수의 Flow chart를 그려보면, 어렵지 않게 규칙을 발견해낼 수 있다.

F(N) = N번쨰 피보나치 수 일때, 0과 1의 호출횟수.

F(N) = ( zero ,one ) 이라고 생각하고, zero = 0 호출횟수 , one = 1 호출횟수 .

• F(0) = ( 1, 0 )
• F(1) = ( 0, 1 )
• F(2) = ( 1, 1 )
• F(3) = F(2) + F (1) = (1, 2)
• F(4) = F(3) + F (2) = ( 2, 3 )

이런 식으로, 호출이 된다.

bottom up 방식이든 , top down 방식이든 상관 없을거 같아서, 두가지 방법 모두로 풀어보겠음.

 

#TOP - down
#memoization 이용.
import sys

dp = [0] * 41

def fibo(n):
    #print(dp)
    if dp[n] != 0:
        return dp[n]
    if n<2:
        return n
    else:
        dp[n] = fibo(n-1)+fibo(n-2)
        return dp[n]
    

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

for i in range(T):
    case = int(sys.stdin.readline())
    
    if case == 0:
        print(1,0)
    elif case == 1:
        print(0,1)
    else:
        print(fibo(case-1),fibo(case))

#bottom up
#2차원 배열로 생각해줬음. (DP[0][n] 0의 갯수, DP[1][n] 1의 갯수)
tc=int(input())
DP = [[0]*41 for _ in range(2)]

while tc:
    n= int(input())
    DP[0][0] = 1
    DP[1][0] = 0
    DP[0][1] = 0
    DP[1][1] = 1
    if n ==0:
        print(DP[0][0],DP[1][0])
    elif n ==1:
        print(DP[0][1],DP[1][1])
    else:
        for i in range(2,n+1):
            DP[0][i] = DP[0][i-2] + DP[0][i-1]
            DP[1][i] = DP[1][i-2] + DP[1][i-1]
        print(DP[0][n],DP[1][n])
    tc-=1