BOJ 1003. 피보나치 함수 (Python)

문제

BOJ 1003

 

내가 생각한 풀이

fibonacci(N)을 호출했을 때, 0과 1이 몇 번 출력되는지 구하는 프로그램.

 

fibonacci(0)과 fibonacci(1)이 몇 번 수행되는지 구하는 프로그램인데 시간 제한이 0.25초라서 일반적인 풀이로는 시간초과가 난다.

DP를 사용하면 짧은 시간 내에 풀 수 있음.

dp[0]은 fibonacci(0)을 호출할 때 fibonacci(0) 과 fibonacci(1)이 수행될 횟수 => (1, 0)

dp[1]은 fibonacci(1)을 호출할 때 fibonacci(0) 과 fibonacci(1)이 수행될 횟수 => (0, 1)

dp[2]는 fibonacci(2)를 호출할 때 fibonacci(0) 과 fibonacci(1)이 수행될 횟수 => (1, 1), fibo(1) + fibo(0)

dp[3]은 fibonacci(3)을 호출할 때 fibonacci(0) 과 fibonacci(1)이 수행될 횟수 => (1, 2), fibo(2) + fibo(1)

dp[4]는 fibonacci(4)를 호출할 때 fibonacci(0) 과 fibonacci(1)이 수행될 횟수 => (2, 3), fibo(3) + fibo(2)

 

테이블 정의

dp는 dp[i-1] + dp[i-2]

점화식

dp[i] = tuple(dp[i-1][0] + dp[i-2][0], dp[i-1][1] + dp[i-2][1])

 

코드 (Python)

import sys
input = sys.stdin.readline

T = int(input().strip())

dp = [(1, 0), (0, 1)]
for i in range(2, 41):
    a0, a1 = dp[i-1]
    b0, b1 = dp[i-2]
    dp.append((a0 + b0, a1 + b1))

for _ in range(T):
    n = int(input().strip())
    print(*dp[n])