알고리즘
python 백준2748 피보나치 수 2(BOJ2748)
피프밍
2023. 1. 3. 07:39
문제링크 : https://www.acmicpc.net/problem/2748
2748번: 피보나치 수 2
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가
www.acmicpc.net
for문에 별찍기가 있다면
dp에는 피보나치가 있다!@!
정말 가장 기본적인 구조인데 이 구조를 다른문제에도 적용하는게 어렵다..
점화식을 구하고 어디까지 초기값으로 잡고 어느구간에서부터 반복문으로 돌릴지를 파악하는게 핵심인것같다
알면 뭐하나.. 잘 안되는걸ㅜㅜ
import sys
input = sys.stdin.readline
#메모이제이션dp테이블
dp = [0] * 91
#초기값
dp[1] = 1
dp[2] = 1
n = int(input())
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-2]
print(dp[n])