BOJ 2748번: 피보나치 수 2

www.acmicpc.net/problem/2748

2748번: 피보나치 수 2

아이디어:

DP의 기본 문제

DP의 핵심은 부분 문제로 나누는 것 + Memorization

일반적인 재귀함수로 풀면 이미 계산한 것을 또 다시 계산해야 하는 비효율성 발생 -> 계산한 값을 저장하는 배열을 만들어 활용!

 

import sys
n = int(sys.stdin.readline())
dp = [-1 for _ in range(n+1)]

def solve(n):
    if (dp[n]!=-1):
        return dp[n]
    elif (n<2):
        dp[n]=n
        return n
    else:
        dp[n]=solve(n-1)+solve(n-2)
        return dp[n]
print(solve(n))