문제링크 : 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])'알고리즘' 카테고리의 다른 글
| python 백준9655 돌게임(BOJ9655) (0) | 2023.01.08 |
|---|---|
| python 백준1010 다리 놓기(BOJ1010) (1) | 2023.01.04 |
| python 백준2775 부녀회장이 될테야(BOJ2775) (0) | 2023.01.02 |
| python 백준11000 강의실 배정(BOJ11000) (0) | 2022.12.31 |
| python 백준15686 치킨 배달(BOJ15686) (0) | 2022.12.29 |
