백준17175 - 피보나치는 지겨웡~

https://www.acmicpc.net/problem/17175

17175번: 피보나치는 지겨웡~

오랜만에 풀어본 dp문제였다. 피보나치를 물어 봤으니 반드시 dp로 풀어야 시간초과가 나지 않는다. 항상 염두할 것은 숫자가 커질수록 함수의 결과를 얻어내기까지 시간이 무척이나 오래 걸리기 때문에 그 점을 고려하여 미리 사용했던 결과를 이용해야 된다는 것이다. 결론은 dP문제는 규칙을 찾자!

 

#include <iostream>
using namespace std;

long long int dp[51];

//dp 설계, 0번째와 1번째는 1로 지정하고 나머지는 n - 2번째 + n - 1번째 + 1로 결과를 구한다.
int find_dp(int n) {
	if (n == 0) {
		dp[n] = 1;
		return dp[n];
	}
	if (n == 1) {
		dp[n] = 1;
		return dp[n];
	}
	else {
		dp[n] = (dp[n - 2] + dp[n - 1] + 1) % 1000000007; //전에 사용했던 값을 이용하여 도출, 숫자가 커질 수 있어 십억 칠로 나눈 나머지를 이용
		return dp[n];
	}
}

int main() {
	int n;
	cin >> n;
	for (int i = 0; i <= 50; i++) { //0번째부터 50번째까지 결과를 구해야한다. 그래야 전에 구했던 값을 이용할 수 있다.
		find_dp(i);
	}
	cout << dp[n]; //n번째 결과 출력
}