Search
Duplicate
📗

피보나치는 지겨웡~

주차
문제번호
17175
언어
C++
티어
실버
유형
DP
nj_Blog
nj_상태
이해도
100%
풀이
사람
이해도 2
13 more properties

문제접근

fibo를 부른 횟수를 dp에 저장하면됨

놓쳤던 부분

메모이제이션을 하지 않으면 시간초과
전역변수 배열을 {-1,}로 초기화 하면 안됨

코드

2020 KB

0 ms

#include <iostream> #include <cstring> using namespace std; int dp[51]; int fibonacci(int n) { if (dp[n] != -1) return n; dp[n] = (dp[n - 2] + dp[n - 1] + 1) % 1000000007; return fibonacci(n - 2) + fibonacci(n - 1); } int main(void) { int n; ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); memset(dp, -1, sizeof(dp)); cin >> n; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i++) fibonacci(i); cout << dp[n]; return (0); }
C++
복사