백준 1003 피보나치 함수

문제 : https://www.acmicpc.net/problem/1003

 

서론

DP문제이며 메모이제이션을 이용하여 풀이했다.

 

---

아이디어

n	0	1	2	3	4	5	6	7	8
피보나치	0	1	1	2	3	5	8	13	21
0의 개수	1	0	1	1	2	3	5	8	13
1의 개수	0	1	1	2	3	5	8	13	21

위 표를 보면 규칙성이 있는데,

피보나치 수열과 1의 개수 수열은 같다.

n이 0일때를 제외하고, 피보나치 수열의 n은 0의 개수 수열의 n+1과 같다.

따라서 0의 개수는 n번째 피보나치수를, 1의 개수는 n-1번째 피보나치 수를 출력하면 된다.

 

메모이제이션

함수에서 fib(n) = fib(n-1) + fib(n-2)를 계산할때

이미 fib(n-1)과 fib(n-2)를 이전에 계산한적이 있어서 배열에 저장해두었다면 굳이 함수에 들어가지 않고 바로 배열의 결과를 가져오면 되므로 시간을 절약할 수 있다.  

 

---

구현

1번풀이, 실행시간 4ms

// c++

#include <iostream>
#include <cstring>

using namespace std;

int result[41];

int fib(int n) {
	if (n == 0) {
		result[0] = 0;
		return 0;
	}
	else if (n == 1) {
		result[1] = 1;
		return 1;
	}
	else {
		if (result[n] != 0) return result[n];
		return result[n] = fib(n - 1) + fib(n - 2);
	}
}

int main() {
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		memset(result, 0, sizeof(result));
		int n;
		cin >> n;
		fib(n);
		if (n == 0) cout << "1 0" << endl;
		else cout << result[n-1] << " " << result[n] << endl;
	}
}

 

2번풀이, 실행시간 4ms

fib(n)이 메모이제이션되었는지 검사하지 않고

그 전단계인 fib(n-1)과 fib(n-2)를 각각 메모이제이션되었는지 검사한다.

실행시간에 차이가 있는지 확인하려 했으나 1번풀이와 차이 없음

// c++

#include <iostream>
#include <cstring>

using namespace std;

int result[40];

int fib(int n) {
	if (n == 0) {
		result[0] = 0;
		return 0;
	}
	else if (n == 1) {
		result[1] = 1;
		return 1;
	}
	else {
		int first = 0;
		int second = 0;
		if (result[n - 1] != 0) first = result[n - 1];
		else first = fib(n - 1);
		if (result[n - 2] != 0) second = result[n - 2];
		else second = fib(n - 2);
		return result[n] = first + second;
	}
}

int main() {
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		memset(result, 0, sizeof(result));
		int n;
		cin >> n;
		fib(n);
		if (n == 0) cout << "1 0" << endl;
		else cout << result[n-1] << " " << result[n] << endl;
	}
}

 

3번풀이, 실행시간 4ms

함수가 아닌 반복문 사용, 실행시간 위와 동일

//c++

#include <iostream>

using namespace std;

int main() {
	int t;
	cin >> t;

	for (int i = 0; i < t; i++) {
		int n;
		cin >> n;
		int fibo[50][2];
		fibo[0][0] = 1;
		fibo[0][1] = 0;
		fibo[1][0] = 0;
		fibo[1][1] = 1;

		for (int j = 2; j <= n; j++) {
			fibo[j][0] = fibo[j - 1][0] + fibo[j - 2][0];
			fibo[j][1] = fibo[j - 1][1] + fibo[j - 2][1];
		}

		cout << fibo[n][0] << ' ' << fibo[n][1] << endl;
	}

}