[백준] 17175번: 피보나치는 지겨웡~ [C++]

 

알고리즘 분류: 다이나믹 프로그래밍

문제 링크: https://www.acmicpc.net/problem/17175

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

 

 

【 풀이 】

 

피보나치 함수의 호출 횟수를 출력하는 문제이다.

문제의 코드에 호출될 때마다 횟수를 더해주는 코드를 작성해서 그 횟수를 출력하면 당연히 시간 복잡도에 걸려 시간 초과가 발생하게 된다.

하지만 그 횟수 출력으로 우리가 따로 횟수를 확인해 규칙을 찾고 점화식을 도출해 동적계획법으로 해결하면 된다.

규칙을 찾아본 결과

 

n[0] = 1

n[1] = 1

n[2] = 3

n[3] = 5

n[4] = 9

n[5] = 15

n[6] = 25

n[7] = 41 ...

 

이를 토대로 점화식을 도출해 보면

 

n[i] = n[i-2] + n[i-1] + 1 이다.

 

 

 

 

【 코드 】

#include<iostream>
using namespace std;

long long int f[51];
int main(void) {
	f[0] = 1;
	f[1] = 1;
	int n;
	cin >> n;
	for (int i = 2; i <= 50; i++) {
		f[i] = f[i - 2] + f[i - 1] + 1;
	}
	cout << f[n] % 1000000007;
	return 0;
}