백준 1003번: 피보나치 함수 / C++

어떤 문제일까?

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

 

문제에서 다음과 같이 피보나치 함수에 대한 소스를 제공해주었다

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

 

문제를 푸는데 아무 쓸모도 없었다

그냥 0과 1의 개수를 구하기 위해 피보나치로 풀어야하고, 시간복잡도 때문에 DP를 써야하는구나를 알 수 있었다.

엥 지금 다시 글을 쓰면서 생각해보니 쓸모가 있었다

 

피보나치 함수 DP로 만들기

int fibonacci(int n) {
	dp[0] = 0;
	dp[1] = 1;
	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	return dp[n];
}

 

구글링 했을 때 나오는 피보나치 함수 틀은 위와 같다.

나는 0과 1의 개수를 세야하므로 피보나치 함수를 2개 만들어주었다.

이유는 0과 1의 개수가 약간의 차이가 있었기 때문이다.

 

0의 개수
1 0 1 1 2 3 5 8 13 21

1의 개수
0 1 1 2 3 5 8 13 21 34

 

이렇게 차이가 있었다.

 

해결

#include <iostream>
using namespace std;

int dpZero[50];
int dpOne[50];

int fibonacciZero(int n) {
	dpZero[0] = 1;
	dpZero[1] = 0;
	dpZero[2] = 1;
	for (int i = 3; i <= n; i++) {
		dpZero[i] = dpZero[i - 1] + dpZero[i - 2];
	}
	return dpZero[n];
}

int fibonacciOne(int m) {
	dpOne[0] = 0;
	dpOne[1] = 1;
	for (int i = 2; i <= m; i++) {
		dpOne[i] = dpOne[i - 1] + dpOne[i - 2];
	}
	return dpOne[m];
}

int main() {
	int t, num;
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> num;
		cout << fibonacciZero(num) << " " << fibonacciOne(num) << "\n";
		
	}
	
	return 0;
}