[백준 알고리즘] 17175번 : 피보나치는 지겨웡~

문제

혁진이는 알고리즘 문제를 만들라는 독촉을 받아 스트레스다. 하지만 피보나치 문제는 너무 많이 봐서 지겹기 그지없다. 그러나 문제를 만들 시간이 없는 혁진이는 피보나치 문제를 응용해서 문제를 만들려 한다.

int fibonacci(int n) { // 호출 
	if (n < 2) { 
    	return n; 
	} 
    return fibonacci(n-2) + fibonacci(n-1);
}

위와 같이 코딩하였을 때 fibonacci(n)를 입력했을 때에 fibonacci 함수가 호출되는 횟수를 계산해보자.

입력

fibonacci 함수에 인자로 입력할 n이 주어진다. (0 ≤ n ≤ 50)

출력

fibonacci 함수가 호출된 횟수를 출력한다.
출력값이 매우 커질 수 있으므로 정답을 1,000,000,007 로 나눈 나머지를 출력한다.

예제 입력 1

2

예제 출력 1

3

예제 입력 2

3

예제 출력 2

5

출처

University > 충남대학교 > 제3회 생각하는 프로그래밍 대회 C번

 

내가 작성한 코드 (C++ 성공)

#include <iostream>

using namespace std;

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

 

정리

피보나치는 동적 계획법으로 정말 많은 예제로 나와있기 때문에
동적 계획법으로 풀 수 있었다.
사실 처음에는 재귀 함수를 이용해서 풀다가 시간초과가 나와서 동적계획법으로 풀었다. ㅎㅎ