c++ 백준 1003번 피보나치 함수

문제

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

풀이 방법

fibonacci(3)이 0을 호출 하는 횟수는 fibonacci(2)가 0을 호출하는 횟수 + fibonacci(1)이 0을 호출하는 횟수이다.

fibonacci(3)이 1을 호출 하는 횟수는 fibonacci(2)가 1을 호출하는 횟수 + fibonacci(1)이 1을 호출하는 횟수이다.

 

즉, fibonacci(n)이 0을 호출하는 횟수 = fibonacci(n-1)이 0을 호출하는 횟수 + fibonacci(n-2)가 0을 호출하는 횟수

 

각 횟수를 저장하는 array를 만들었고, testCase를 입력받기 전에 미리 40까지의 모든 횟수를 계산해뒀다.

 

 

구현 코드

#include <stdio.h>

int main()
{
	int fib0Count[41] = { 1, 0 };
	int fib1Count[41] = { 0, 1 };

	for (int i = 2; i < 41; i++)
	{
		fib0Count[i] = fib0Count[i - 1] + fib0Count[i - 2];
		fib1Count[i] = fib1Count[i - 1] + fib1Count[i - 2];
	}

	int testCase = 0;
	scanf("%d", &testCase);

	for (int i = 0; i < testCase; i++)
	{
		int n = 0;
		scanf("%d", &n);

		printf("%d %d\n", fib0Count[n], fib1Count[n]);
	}

	return 0;
}

 

 

DP 풀이용

이번엔 단순 연산으로 풀었는데 과거에는 DP로 풀었었네?

메모리나 시간으로 보면 당연히 단순 연산이 빠르다. 근데 DP공부 목적으로 푼거라면 아래의 해결방법을 살펴보는 걸 추천한다.

현재 코드 (단순연산)

과거 코드 (DP)

flower0.tistory.com/60

[성실코딩 3일차] 백준 #1003 피보나치 함수 / DP &s