https://www.acmicpc.net/problem/17175
17175번: 피보나치는 지겨웡~
혁진이는 알고리즘 문제를 만들라는 독촉을 받아 스트레스다. 하지만 피보나치 문제는 너무 많이 봐서 지겹기 그지없다. 그러나 문제를 만들 시간이 없는 혁진이는 피보나치 문제를 응용해서
www.acmicpc.net
1차원 DP 문제였다.
피보나치 함수(이하 fibo) 의 호출횟수를 수동으로 살펴보도록 하겠다.
fibo[0] = 1
fibo[1] = 1
fibo[2] = 3
fibo[3] = 5
fibo[4] = 9
....
규칙을 파악할 수 있는가?
fibo[k] = (1+fibo[k-1]+fibo[k-2]) 이다.
1은 자기자신 역시 호출되었기에 더해줘야 하는 수고
fibo[k-1]과 fibo[k-2] 는 fibonacci(k) 가 호출하는 함수들이 호출하는 횟수이다.
정답이 커질수 있으니 계산 중간중간에 1e9+7으로 나눠서 출력해주면 정답을 받을 수 있다.
#include <bits/stdc++.h>
using namespace std;
int cnt[60] = {0};
int main(){
cnt[0] = cnt[1] = 1;
for(int i=2; i<=50; i++){
cnt[i] = (1+cnt[i-1]+cnt[i-2]) % 1000000007;
}
int n;
cin >> n;
cout << cnt[n];
return 0;
}
반응형