[백준 알고리즘 C++] 1003번 피보나치 함수

문제를 보면 뭔가 복잡하게 막 나열되어 있는 것을 볼 수 있다.

하지만 피보나치의 원리만 이해한다면 제시되어 있는 소스코드가 무엇인지 알 수 있다.

그럼 문제를 풀기 전, 피보나치 수열이 무엇인지 부터 알아보겠다.

 

=========================================================

피보나치 수열이란?

단순하게 수를 표현해보면 A, B, C, D, E, F 라는 수가 나열되어 있다.

이때 피보나치 수열이라면 일정한 조건을 가지고 있는데,

바로 앞의 두수의 합이 다음 수가 된다는 조건이다.

 

그래서 이런 피보나치 수열은 기본적으로 첫번째, 두번째 수는 1로 정해져있다.

그 다음수는 앞의 두수를 더하여 만들어 낼 수 있다.

이 논리로 피보나치 수열을 아래와 같이 나열할 수 있다.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ....... 

=========================================================

 

이제 이런 논리를 코드로 만들어야 한다.

문제에 제시되어 있는 코드를 보면 n=0, n=1 일때는 각각 합이 0과 1로 바로 리턴해주고 있다.

그 다음 부터는 fibonacc1(n-1) + fibonacc1(n-2) 를 더하여 리턴하고 있다.

즉, 앞선 두 수를 더하는 것이다. 

 

하지만 이 문제에서는 재귀로 할 경우 아마 시간초과가 날 것이다.

시간제한이 0.25초로 준것은 분명 재귀로 풀면 시간초과가 나니 다른 방법을 생각해라!

라는 고민거리를 안겨준 것이다.

그래서 이 문제는 점화식을 이용한 DP(다이나믹프로그래밍) 방법을 이용해야한다.

 

자, 그럼 점화식을 만들어 보자

N	fibonacci(0)의 호출 수	fibonacci(1)의 호출 수
0	1	0
1	0	1
2	1	1
3	1	2

위의 표에서 점화식을 구할 수 있습니다.

fibonacci(0)의 호출 수와 fibonacci(1)의 호출 수는 일정한 규칙이 존재하는데,

N=3 일때를 보면 답은 N이 2일때와 1일때의 합인것을 알 수 있습니다.

그래서 아래와 같이 점화식으로 나타낼 수 있습니다.

f(n) = f(n-1) + f(n-2) (단 n = 0, 1이 아닐때)

 

이제 이것을 소스로 풀어보겠습니다.

저는 num_zero와 num_one 이라는 0과 1이 호출되는 수를 담은 배열을 선언했습니다.

그리고 기본값으로 n이 0일때와 1일때는 값을 넣어줬습니다.

그리고 n만큼 for문을 돌면서 num_zero[n] 과 num_one[n]을 리턴해주고 있습니다.

#include 
using namespace std;
long long num_zero[41];
long long num_one[41];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t;
	cin >> t;
	
	num_zero[0] = 1;
	num_one[0] = 0;
	num_zero[1] = 0;
	num_one[1] = 1;
	
	while(t--){
		int n;
		cin >> n;
		
		if(n == 0){
			cout << num_zero[0] << " " << num_one[0] << "\n";
		}
		else if(n == 1){
			cout << num_zero[1] << " " << num_one[1] << "\n";
		}
		else{
			for(int i=2; i<=n; i++){
				num_zero[i] = num_zero[i-1] + num_zero[i-2];
				num_one[i] = num_one[i-1] + num_one[i-2];
			}
		
			cout << num_zero[n] << " " << num_one[n] << "\n";
		}
		
	}
	
	return 0;
}

 

피보나치 수열 문제라기 보다는 그것을 좀 응용하여 피보나치 수열의 원리를 파악해볼 수 있는 문제였던 것 같네요.