[BOJ] 백준 2748 피보나치 수 2 , 백준 1003 피보나치 함수 파이썬 풀이

#정답은 여러가지일 수 있음

##파이썬으로 풀었다

### 질문 댓글

####문제는 따로 쓰지않음

 

 

피보나치 수란 ???

0과 1로 시작을 해 0번째 피보나치 수는 0이고 1번쨰는 1이다 그 다음부터는 바로 앞의 두 피보나치 수의 합이 된다

0,1,2,3,5,8,13 . . . 이런식으로 증가해 나간다 

 

 

2748- 피보나치 수 2

피보나치 수열
def dp(n):
    for i in range(2,n+1):
        arr.append(arr[i-1]+arr[i-2])
    return(arr[n])

n=int(input())
arr=[0,1]
print(dp(n))

 

점화식은 arr[i] = arr[i-1]+arr[i-2] 가 된다 이때 단순재귀를 이용하면 함수 호출개수가 너무 많아지기 때문에 for문을 이용하자

 

1003- 피보나치 함수

이 문제의 포인트는 

f(0) = 0

f(1) = 1

f(2)  = f(0) + f(1) = 0 + 1

f(3) = f(2) + f(1) = 0+1   1

. . .

 

이렇게 보면

	0	1	2	3	4
0	1	0	1(0+1)	1(1+2)	2(2+3)
1	0	1	1(0+1)	2(1+2)	3(2+3)

이렇게 각 0과 1에 대해서도 피보나치수가 된다는 것이 포인트이다 

 

def f(n):
    for i in range(2,n+1):
        zero.append(zero[i-1]+zero[i-2])
        one.append(one[i-1]+one[i-2])
    return zero[n],one[n]

testCase = int(input())
for i in range(testCase):
    n= int(input())
    zero=[1,0]
    one = [0,1]
    
    num1,num2 = f(n)
    print(num1,num2)