백준 1003번 파이썬 | 피보나치 함수 (DP)

문제

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

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

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

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

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

---

풀이

이 문제는 시간 제한이 0.25이기때문에 일반적인 재귀함수로 풀면 안된다.

동적 계획법을 사용해서 풀어야 하며 규칙을 찾으면 쉽게 풀 수 있다.

여기서 0과 1이 호출된 수를 찾아야 하는데 이를 하나씩 적어보면 다음과 같은 규칙을 찾을 수 있다.

0일때 1 0

1일때 0 1

2일때 1 1

3일때 1 2

4일때 2 3

5일때 3 5

6일때 5 8

..

즉, 0이 호출된 수는  피보나츠에서 (n-1)값이고 ( 0 1 1 2 3 5..)

1이 호출된 수는 피보나츠에서 n값이다. (0 1 1 2 3 5 8 ...)

따라서 0일때, 1일때만 체크해주고 나머지는 fibo(n-1) + fibo(n) 으로 하면 된다.

 

Dp를 풀때는 list 형식으로 모두 0을 저장한 뒤에 같은 계산을 반복하지 않도록 이미 계산된 수이면 바로 그 수를 쓰도록 따로 저장해두면 된다. 그러면 O(n)으로 풀 수 있기 때문에 빠른 시간내에 문제를 해결할 수 있다.

# 1003 피보나치 함수
# DP

import sys
input = sys.stdin.readline


def fibo(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    if d[n] != 0:
        return d[n]
    d[n] = fibo(n - 1) + fibo(n - 2)
    return d[n]


T = int(input())
d = [0] * 41

for i in range(T):
    N = int(input())
    fibo(N)
    if N == 0:
        print(1, 0)
    elif N == 1:
        print(0, 1)
    else:
        print(fibo(N - 1), fibo(N))