(Python/파이썬) 백준 1003번 - 피보나치 함수

문제출처: https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

1. 코드

zero = [1,0,1]
one = [0,1,1]
 
for i in range(3,41):
    zero.append(zero[i-1]+zero[i-2])
    one.append(one[i-1]+one[i-2])
 
 
test = int(input())
 
for i in range(test):
    n = int(input())
    print(zero[n], one[n])
 

2. 해결과정

피보나치 함수에서 0과 1이 리턴되는 횟수를 구하는 문제이다.

 fibonacci(n)을 호출한다면, 실행되는 fibonacci(0)과 fibonacci(1)은 'fibonacci(n-1)의 0과 1 호출 횟수' + 'fibonacci(n-2)의 0과 1 호출 횟수'와 동일하다.

따라서 같은 방식으로 호출 횟수를 구해주면 된다.

zero와 one 배열에 미리 n이 0~2까지일 경우에 호출되는 횟수를 넣어주고, 그 후부터는 계산을 해서 넣어주게 설정하였다.

 

3. 느낀점

간단하게 dp를 이용해서 풀 수 있었던 문제