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

 

1003번: 피보나치 함수

 

 

N이 주어졌을때 피보나치 함수에서 0과 1이 출력되는 횟수를 알아내야하는게 핵심

문제에서 주어진 함수를 이용해서 재귀로 문제를 푼다면 시간초과가 발생한다

따라서 DP로 해결해야한다

 

피보나치 함수

 

0과1 횟수는 피보나치 성격을 갖기때문에 동일한 규칙을 갖는다

fib(n)에서 1과 0의 개수 2개를 저장해줘야 하므로 2차원으로 구현해야한다

 

import sys
testcase = int(sys.stdin.readline())
for i in range(testcase):
    N = int(sys.stdin.readline())
    dp = [[0] * 2 for _ in range(N+1)]
    dp[0][0] = 1
    dp[0][1] = 0
    if N>0:
        dp[1][0] = 0
        dp[1][1] = 1
        for i in range(2,N+1):
            dp[i][0] = dp[i-1][0] + dp[i-2][0] 
            dp[i][1] = dp[i-1][1] + dp[i-2][1] 
    sys.stdout.write(f"{dp[N][0]} {dp[N][1]}\n")

 

제출한 코드