[C/C++] 백준 알고리즘 수업 - 피보나치 문제 모음

✏️ 문제 링크

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

 

 

✏️ 문제 설명

 

 

✏️ 문제 풀이

피보나치 함수를 재귀함수와 동적프로그래밍으로 계산했을 때 각 함수를 얼마나 호출하는지에 관한 문제입니다.

전역변수로 cnt1을 선언하고 재귀함수 부분에서 return (fib(n - 1) + fib(n - 2));을 호출하기 직전에 cnt1에 1을 더해주시면 됩니다. 차피 n==1일때나 2일때까지 가고나면 알아서 계산을 다 해주기 때문에 이렇게 재귀 호출 횟수를 구할 수 있습니다

 

동적 프로그래밍으로 하는 계산횟수는 for문을 돌리기보다 쉽게 생각해보면 n-2번 호출하게 됩니다.

fib(n)값을 구하기 전에 미리 fib(1)과 fib(2)값을 지정해놓기 때문에 위의 사진처럼 for문을 돌린다면 

1번째 값, 2번째 값을 빼놓고 계산을 하게 되므로 호출 횟수는 n-2입니다.

 

✏️ 문제 코드

#include<iostream>
using namespace std;

int cnt1 = 0, cnt2 = 0;
int fib(int n);
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;
	fib(n);

	cout << cnt1+1 << " " << n-2;
}
int fib(int n) {
	if (n == 1 || n == 2) {
		return 1;
	}

	else {
		cnt1++;
		return (fib(n - 1) + fib(n - 2));
	}
}

 

 

 

✏️ 문제 링크

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

 

 

✏️ 문제 설명

 

 

✏️ 문제 풀이

24416번과 비슷하지만 이번엔 n의 범위가 더 커졌습니다. 그리고 mod연산도 추가로 해야 합니다.

우선 동적 프로그래밍의 호출 횟수는 위의 문제와 동일하게 n-2번이고, 출력할 때는 1,000,000,007로 나눠야 합니다

다음은 재귀 함수의 호출 횟수인데, 처음에는 24416번의 재귀 호출로 하였는데 메모리 초과가 떴습니다.

아마 n이 커져서 계속해서 힙에 메모리를 쌓다 보니까 메모리 초과가 나는 것 같습니다.

 

그래서 배열을 이용해서 for문을 돌렸습니다. 처음에는 20000001개의 크기를 가진 배열로 문제를 풀었는데

outofbounds가 나서 다시 방식을 바꿨습니다. long long형 a,b,c를 각각 0,1,1로 지정해놓고

n-2번의 for문을 돌리면서 각각

a = b%1000000007;
b = c%1000000007;
c = (a%1000000007 + b%1000000007)%1000000007; 로 갱신을 해줬습니다.

배열을 쓰는 대신 숫자 3개를 이용해서 접근을 하였습니다.

 

 

✏️ 문제 코드

#include<iostream>
using namespace std;

int main() {
	int n;
	cin>> n;
	
	long long a, b, c;
	a = 0;
	b = 1;
	c = 1;
	
	
	for(int i= 0; i<n-2; i++){
		a = b%1000000007;
		b = c%1000000007;
	    c = (a%1000000007 + b%1000000007)%1000000007;
	}

	
	cout<< c <<" "<<n-2;
	return 0;
}