7300 : 재귀 심화 종합 2
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
피보나치 유사 점화식 $f(n) = f(n-1) + f(n-2) + f(n-3)$($f(0)=0$, $f(1)=f(2)=1$)의 $N$번째 값을 구하십시오.
분할 정복과 메모이제이션을 결합하여 효율적으로 계산합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
분할 정복과 메모이제이션을 결합하여 효율적으로 계산합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 $N$이 주어집니다. ($0 \le N \le 1{,}000$)
출력 설명
$f(N) \bmod (10^9+7)$을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
10
출력 예시
COPY
복사되었습니다!
복사되었습니다!
274도움
memo = {}; def f(n): if n in memo: return memo[n]; if n <= 2: return n if n > 0 else 0; memo[n]=(f(n-1)+f(n-2)+f(n-3))%MOD; return memo[n]