[BOJ] 10870: 피보나치 수 5

🔒 예제

>> 10

55

🔧 풀이

1. n = int(sys.stdin.readline().rstrip())
2. dp
	2.1 dp 배열 
    2.2 수열 :: f(n) = f(n-1) + f(n-2) (n>=2)
3. n < 2 일 때 예외 처리 ***

🔑 답안

import sys

n = int(sys.stdin.readline().rstrip())
dp = [0 for i in range(n+1)]

if n < 2:
	print(n)
else:
	dp[0] = 0
	dp[1] = 1
	for i in range(2, n+1):
		dp[i] = dp[i-1] + dp[i-2]
	print(dp[n])

💡 개념

### dynamic programming
- 문제 속 소문제의 반복 :: 규칙(수열) 찾기
	ㄴ 필요에 따라 케이스 나누기
- memoization :: dp = []

좋은 웹페이지 즐겨찾기