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

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

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

1003번: 피보나치 함수

실버 3

DP

---

접근

문제에서 써져 있는 재귀함수 방법 그대로 날먹하면 시간초과 당한다...

import sys

zero_cnt = 0

one_cnt = 0
def fibo(x):
    global zero_cnt
    global one_cnt
    if x == 0:
        zero_cnt += 1
        return 0
    elif x == 1:
        one_cnt += 1
        return 1
    else:
        return fibo(x-1) + fibo(x-2)

t = int(sys.stdin.readline())
for i in range(t):
    n = int(sys.stdin.readline())
    fibo(n)
    print(zero_cnt, one_cnt)
    zero_cnt, one_cnt = 0, 0

 

나는 위의 방법을 통해 전역변수로 0과 1의 경우를 카운트하고 출력하도록 했으나 바로 시간초과 당했다.

대신 이 코드를 사용해 0~7까지의 값을 입력하니 다음과 같은 결과를 얻을 수 있었다.

n : 0 -> 1, 0

n : 1 -> 0, 1

n : 2 -> 1, 1

n : 3 -> 1, 2

n : 4 -> 2, 3

n : 5 -> 3, 5

n : 6 -> 5, 8

n : 7 -> 8, 13

 

n : 0인 경우을 제외하면 피보나치 수열과 같다는 사실을 발견할 수 있었다.

 

코드

import sys; input = sys.stdin.readline
t = int(input())
for _ in range(t):
    prime = [0] * 41
    prime[1] = 1
    n = int(input())
    if n == 0:
        print(1, 0)
    else:
        for i in range(2, n+1):
            prime[i] = prime[i-1] + prime[i-2]
        print(prime[n-1], prime[n])

 

재귀함수를 이용해 피보나치 수열을 구현하면 값이 조금만 커져도 필요한 값을 구하는 속도가 기하급수적으로 증가하므로 메모리제이션을 활용한 보톰업 방식을 사용해 문제를 구현했다.

n : 0인 경우는 예외인 값을 바로 출력하도록 했다.