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

백준 1003번 문제 write-up입니다.

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

1003번: 피보나치 함수

---

피보나치 함수 문제입니다.

다만, 문제에는 피보나치 수열의 결과가 아니라 각 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 출력하라고 되어 있습니다.

 

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(0) = 0, fibonacci(1) = 1을 반환합니다.

fibonacci(n)은 fibonacci(n - 1) + fibonacci(n - 2)을 호출합니다.

 

n = 2이면, fibonacci(2) = fibonacci(0) + fibonacci(1)입니다.

fibonacci(0)가 0이고, fibonacci(1)이 1입니다. 0과 1이 하나씩 나왔기 때문에, 결과는 1 1 입니다.

 

n = 3이면, fibonacci(3) = fibonacci(1) + fibonacci(2)입니다.

이 때, fibonacci(2) = fibonacci(0) + fibonacci(1)이므로

fibonacci(3) = fibonacci(1) + fibonacci(0) + fibonacci(1)가 됩니다.

1 0 1 이렇게 나오기 때문에, 결과는 1 2 입니다.

 

이런 식으로 진행이 되는데, 결국 0과 1의 개수는 fibonacci(0)과 fibonacci(1) 함수의 호출 횟수와 동일하다는 것을 알 수 있습니다.

 

호출 횟수를 구하면 되는데, 각 테스트 케이스마다 재귀함수를 때려 버리면 시간 초과가 발생하기 때문에 동적 계획법으로 코드를 구상해야 합니다.

계산 결과를 저장하는 count 배열을 만들고, n = 0과 n = 1에는 1, 0과 0, 1을 기본값으로 넣어놓습니다.

이후 n값에 따라 fibonacci(n)를 호출하되, 결과를 count에 저장해놓습니다.

만약 이전에 fibonacci(n)을 호출한 적이 있다면, 계산하지 말고 count에서 미리 계산해 놓은 값을 가져옵니다.

이런 식으로 재귀함수 사용을 최소화합니다.

 

해당 풀이로 작성한 코드입니다.

그러나 문제에서 준 fibonacci()함수를 사용하지 않아도 문제를 풀 수 있는데, 아래쪽에 추가적인 풀이가 있습니다.

#include <iostream>
using namespace std;

pair<int, int> count[41] = {make_pair(1, 0), make_pair(0, 1)};

pair<int, int> fibonacci(int n) {
    if (n == 0) {
        return count[n];
    } else if (n == 1) {
        return count[n];
    } else {
    	if(count[n].first) { return count[n]; }
        else {
        	pair<int, int> arr1 = fibonacci(n - 1);
			pair<int, int> arr2 = fibonacci(n - 2);
			pair<int, int> arr = make_pair(arr1.first + arr2.first, arr1.second + arr2.second);
			count[n] = make_pair(arr.first, arr.second);
			return arr;
		}
    }
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t;
	cin >> t;
	for(int i = 0; i < t; i++) {
		int n; cin >> n;
		pair<int, int> res = fibonacci(n);
		cout << res.first << ' ' << res.second << '\n';
	}
}

---

위 풀이법을 그림으로 표현하면 이렇습니다.

[그림 1] 그림으로 표현한 풀이

n = k면, n = k - 2와 n = k - 1의 결과를 더한 결과가 나옵니다.

n 값으로 6이 들어오면, 2부터 시작해서 6까지 해당 배열을 채우고 6의 결과를 출력하면 됩니다.

이후 n이 6보다 작은 값이 들어오면, 계산할 필요 없이 해당 배열에서 바로 꺼내 출력하면 되고

n이 6보다 크다면 7부터 n까지 추가로 계산 후 n의 결과를 출력하면 됩니다.

 

해당 풀이를 이용해 새로 작성한 코드입니다.

#include <iostream>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int count[41][2] = {{1, 0}, {0, 1}};
	int index = 2;
	
	int t;
	cin >> t;
	
	for(int i = 0; i < t; i++) {
		int n; cin >> n;
		if(index <= n) {
			for(index; index <= n; index++) {
				count[index][0] = count[index - 2][0] + count[index - 1][0];
				count[index][1] = count[index - 2][1] + count[index - 1][1];
			}
		}
		cout << count[n][0] << ' ' << count[n][1] << '\n';
	}
}