Skip to main content

[백준] 1003 피보나치 함수

문제​

Alt text

Alt text

코드​

import sys

cases = int(sys.stdin.readline().rstrip())

ans = []

for i in range(cases):
    x = int(sys.stdin.readline().rstrip())
    dp=[[0,0] for _ in range(x+1)]
    dp[0][0] = 1
    dp[0][1] = 0
    if x > 0:
        dp[1][0] = 0
        dp[1][1] = 1
        for i in range(2,x+1):
            dp[i][0] = dp[i-1][0]+dp[i-2][0]
            dp[i][1] = dp[i-1][1]+dp[i-2][1]

    ans.append(dp[x])

for i in ans:
    print(i[0],i[1])

설명​

fibonacci 함수를 사용하면 시간복잡도가 2^n으로 엄~~~청나게 길어집니다.

왜냐하면 재귀함수인데 return으로 재귀함수를 2번 더 호출하기 때문에 호출할수록 2배씩 늘어납니다.

그래서 반복문을 사용해서 해결해야하는데

다이나믹 프로그래밍 문제는 점화식과 초기값 설정을 잘하면 된다고 합니다.

점화식은 dp[n][0] = dp[n-1][0] + dp[n-2][0] 이였고

초기값을 설정하니 정확히 값이 잘 나왔습니다.