2748번: 피보나치 수 2
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가
www.acmicpc.net
아이디어:
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))
'알고리즘💻 > DP' 카테고리의 다른 글
BOJ 14494번: 다이나믹이 뭐예요? (0) | 2021.01.24 |
---|---|
BOJ 20500번: Ezreal 여눈부터 가네 ㅈㅈ (0) | 2021.01.24 |
BOJ 1463번: 1로 만들기 (0) | 2021.01.24 |
BOJ 1757번: 달려달려 (0) | 2021.01.24 |
BOJ 15988번: 1, 2, 3 더하기 3 (0) | 2021.01.24 |