1197 : [기초-재귀설계] 재귀로 n번째 피보나치 수 출력하기(재귀)(메모이제이션)
•시간제한: 1.000 S
•메모리제한: 128 MB
•제출: 10
•통과: 7
•만든사람: suakii
문제 설명
※ 주의: 이 문제는 재귀 설계 문제로서 반복문(for, while)을 사용한 코드는 채점이 되지 않습니다.
n번째 피보나치 수(메모이제이션) 문제를 해결하시오.(단, 반복문은 사용할 수 없다.)
[파이썬 재귀 설계 예시]
memo = {}
def f(n):
if n <= 2: return 1
if n in memo: return memo[n]
memo[n] = (f(n-2) + f(n-1)) % 1000000007
return memo[n]참고
모든 반복은 재귀를 이용해 만들 수 있다! 하향식 설계를 통해 큰 문제를 작은 문제로 쪼개어 해결해 보세요.
입력 설명
정수 형 정수($n$) 1개가 입력된다.
($1 \le n \le 100$)
($1 \le n \le 100$)
출력 설명
$n$번째 피보나치 수를 출력한다.
(단, 수가 매우 크기 때문에 $1000000007$($10$억 $7$)로 나눈 나머지를 출력하도록 한다.)
(단, 수가 매우 크기 때문에 $1000000007$($10$억 $7$)로 나눈 나머지를 출력하도록 한다.)
입력 예시
COPY
복사되었습니다!
복사되었습니다!
6
출력 예시
COPY
복사되었습니다!
복사되었습니다!
8
도움
기초100제(c)2 v1.0 : 정보교사 커뮤니티 @컴퓨터과학사랑(CSL)
- 중고등학교 정보 선생님들과 함께 정보수업/방과후/동아리활동 등을 통해 재미있게 배워보세요.
- 모든 내용 및 이미지들은 저작자와의 협의 없이 무단으로 사용할 수 없습니다.
[원작자: 전현석, 정종광(확인), 배준호(확인) (2016)]
- 중고등학교 정보 선생님들과 함께 정보수업/방과후/동아리활동 등을 통해 재미있게 배워보세요.
- 모든 내용 및 이미지들은 저작자와의 협의 없이 무단으로 사용할 수 없습니다.
[원작자: 전현석, 정종광(확인), 배준호(확인) (2016)]