[ 백준 / Python ] 피보나치의 수

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

DP를 사용하여 푼 풀이

def solved(num):
    dp = [0 for _ in range(46)]
    dp[0] = 0
    dp[1] = 1
    for i in range(2, num+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[num]


print(solved(int(input())))

 

 

재귀로 풀기 위해 시도한 코드들

 

틀린 코드 - 시간 초과

def recursive(num):
    if num == 0:
        return 0
    if num == 1:
        return 1
    return recursive(num - 1) + recursive(num - 2)


n = int(input())
print(recursive(n))

 

 

시간 초과가 난 이유가 뭘까?

위 코드는 그림을 보면 알 수 있듯이, 같은 작업을 많이 반복하게 된다.
Recursive(2)에 대해 한번 구했어도, 계속해서 여러 번 구해야 하기 때문에 시간 초과가 발생한다.
그렇기 때문에 한번 구한 값은 저장하여, 그 값이 이미 계산된 적이 있다면 저장된 값을 활용하면 된다.

 

 

 

 

정답 코드

dp = [0 for _ in range(46)]
def recursive(num):
    if num == 0:
        return 0
    if num == 1:
        return 1
    if dp[num] != 0:
        return dp[num]
    dp[num] = recursive(num - 1) + recursive(num - 2)
    return dp[num]


n = int(input())
print(recursive(n))