[C/C++]백준 1003번 - 피보나치 함수

 

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

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);
    }
}

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

---

접근방식

 

처음에는 그냥 재귀적인 방법으로 접근을 했는데, 시간 초과가 나서 다른 방법이 필요했다.
다이나믹 프로그래밍 방식을 통해서 시간을 줄이면 되겠다 생각하고 코드를 작성했지만, 탑다운 방식으로는 0과1이 출력되는 횟수를 셀 수 없었다.

바텀업 방식으로 접근을 해보니, 이전에 구한 값을 더해주면, 시간안에 풀 수 있는 문제였다.

F(0)과 F(1)은 값이 정해져 있다. (F(n) 함수는 0과 1이 출력되는 횟수를 구하는 함수)

F(2) = F(0) + F(1) 이다.

그러므로 F(N)의 경우는 이전의 단계에서 구한 F(N-1)과 F(N-2)를 더해주면, 된다.

시간복잡도는 O(n)으로 일반적으로 구현하는 재귀적인 방식의 피보나치 함수의 시간복잡도 O(2^n)과 비교해, 크게 향상된 것을 확인 할 수 있다. 

 

코드

#include<iostream>
#include<utility>

using namespace std;

pair<int, int> dp[41];

void countFibo(int n)
{
	dp[0] = make_pair(1, 0);
	dp[1] = make_pair(0, 1);

	for (int i = 2; i <= n; i++) {
		dp[i] = make_pair((dp[i - 1].first + dp[i - 2].first),
			(dp[i - 1].second + dp[i - 2].second));
	}
}

int main()
{
	int T, n;
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> n;
		countFibo(n);
		cout << dp[n].first << ' ' << dp[n].second << '\n';
	}
	return 0;
}

 

좀 더 나은 방식

 

다른 사람은 어떻게 풀었는지 찾아봤는데, 메모리 사용을 절반으로 줄일 수 있는 놀라운 풀이를 봤다.
역시 알고리즘의 세계에는 대단한 사람들이 많다...

 

N에 따라서 0과 1의 횟수에 일정한 규칙이 있었다.

0의 개수가 이전의 1의 개수와 같다...

문제를 풀 때, 왜 이걸 못 봤을까...

 

N에서의 0의 개수는 N-1의 1의 개수와 같다는 상관관계를 이용하면 메모리 사용을 이 전의 방식에서 절반으로 줄일 수 있다.

 

그럼 위의 아이디어를 적용해서 코드를 다시 작성해 보자.

#include <iostream>

using namespace std;

int dp[41] = { 0, 1, 1};

int main()
{
	for (int i = 3; i < 41; i++) dp[i] = dp[i - 1] + dp[i - 2];

	int T;
	int N;
	
	cin >> T;
	
	for (int i = 0; i < T; i++) {
		cin >> N;
		if (N == 0) cout << 1 << ' ' << 0 << '\n';
		else if (N == 1) cout << 0 << ' ' << 1 << '\n';
		else cout << dp[N - 1] << ' ' << dp[N] << '\n';
	}
	return 0;
}

동일한 동작을 하는 코드지만, 메모리가 절반으로 줄었다...

오늘도 하나 배웠네.

 

 

다른 문제의 코드 : https://github.com/DaeeYong/Algorithm-Solution-

DaeeYong/Algorithm-Solution-