백준 1003: 피보나치 함수 (Python)

 

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

1003번: 피보나치 함수

 

처음 코드 - 걍 냅다 계산..

당연히 시간 초과 날 줄 알았음

def fib(n):
    d = [0] * (n + 1)

    if n == 0:
        count[0] += 1
        return 1
    if n == 1:
        count[1] += 1
        return 1
    d[n] = fib(n - 1) + fib(n - 2)
    return d[n]

t = int(input())
for i in range(t):
    n = int(input())
    count = [0, 0]
    fib(n)
    print(count[0], count[1])

 

규칙을 찾았다

피보나치가 fib(n) = fib(n-1) + fib(n-2) 니까

전 계산 결과를 저장해서 불러오면 된다

 

d = [[0, 0] for _ in range(41)]
d[0] = [1, 0]
d[1] = [0, 1]

for i in range(2, 41):
    d[i][0] = d[i-1][0] + d[i-2][0]
    d[i][1] = d[i-1][1] + d[i-2][1]

t = int(input())
for i in range(t):
    n = int(input())
    print(d[n][0], d[n][1])

 

n의 범위가 40까지밖에 안 되기 때문에 테스트 케이스마다 값을 계산하지 않고

처음에 미리 0~40까지의 계산을 모두 끝내놓고 결과를 실행함