7267 : 재귀 피보나치
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
재귀 함수와 메모이제이션을 이용하여 $N$번째 피보나치 수를 계산하십시오.
점화식: $F(1) = 1$, $F(2) = 1$, $F(n) = F(n-1) + F(n-2)$ ($n \ge 3$)
순수 반복문이 아닌 재귀 함수를 사용해야 합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
점화식: $F(1) = 1$, $F(2) = 1$, $F(n) = F(n-1) + F(n-2)$ ($n \ge 3$)
순수 반복문이 아닌 재귀 함수를 사용해야 합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 정수 $N$이 주어집니다. ($1 \le N \le 40$)
출력 설명
$N$번째 피보나치 수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
10
출력 예시
COPY
복사되었습니다!
복사되었습니다!
55도움
메모이제이션:
memo = {} 딕셔너리를 활용하거나 @functools.lru_cache를 사용하면 $O(N)$에 해결 가능합니다.