[BOJ] 1003번 | 피보나치 함수 (C++)

🔗문제 보러가기

 

1003번: 피보나치 함수

 

🧑🏻‍💻풀이 과정

피보나치 함수를 호출했을 때, \( n = 0 \) 또는 \( n = 1 \)일 때의 0과 1의 출력 개수를 세야 합니다.

(즉, 위 문제에서 주어진 소스 코드에서 if(n == 0)과 if (n==1)에 해당할 경우) 

 

1. Top-down 방식으로 DP 배열을 통해 중복 계산 최소화 방법 시도 (실패)

피보나치 함수를 재귀로 구현했을 때의 문제점이 바로 중복 계산입니다. 중복 계산이 이루어지기에 시간이 터무니없이 많이 걸리는 것이고, 이것을 개선하기 위해 DP 배열을 사용하여 이미 계산된 N이라면 계산하지 않는 것이죠.

 

하지만 N == 0 또는 N == 1이 될 때까지 내려가야 하는데, 이미 계산된 N이라고 해서 계산을 중지해버리면 제대로 개수를 셀 수가 없습니다. 그렇다고, 다 내려가 버리면 DP 배열을 쓰는 이유가 없구요.

 

따라서 Top-down 방식에서는 N == 0 또는 N == 1이 될 때까지 다 내려가지 않는 이상, 방법이 없다고 판단하였고, Bottom-up 방식으로 생각을 돌리게 되었습니다.

 

 

2. Bottom-up 방식으로 0과 1의 개수 저장해 가기 (성공)

피보나치 수열의 점화식은 다음과 같습니다.

// fibonacci[0] = fibonacci[1] = 1
fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];  // if) i >= 2

 

재귀로 피보나치 수열을 구하는 함수를 짰을 때, N == 0 또는 N == 1 일 때가 종료 조건이며, 각각 0과 1을 리턴하였습니다.

그리고 fibonacci[i]는 이러한 0과 1들이 다 더해져서 생성된 숫자입니다.

 

즉, 위의 피보나치 수열의 점화식은 0과 1의 개수에서도 적용된다는 의미입니다.

fibonacci[i].zero = fibonacci[i - 1].zero + fibonacci[i - 2].zero;
fibonacci[i].one = fibonacci[i - 1].one + fibonacci[i - 2].one;

 

따라서, DP[i] 배열은 i번째 피보나치 수의 0과 1의 개수를 저장하고 있어야 합니다.

문제 조건에서 입력의 최대 개수가 40개이므로, N = 40까지 DP 배열을 채우도록 하고, 문제에서 입력으로 주어지는 숫자의 인덱스로 찾아가서 답을 추출해 오면 됩니다.

 

✏️소스 코드 및 결과

#include <iostream>
#include <vector>
using namespace std;
using Count = pair<int, int>;   // (0의 개수, 1의 개수)

void SetFastIO()
{
	ios::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
}

int main()
{
	SetFastIO();

	const int MAX_INPUT_SIZE = 41;
	vector<Count> dp(MAX_INPUT_SIZE);
	dp[0] = Count(1, 0), dp[1] = Count(0, 1);

	for (int i = 2; i < MAX_INPUT_SIZE; i++)
	{
		int sumOfZeroCount = dp[i - 1].first + dp[i - 2].first;
		int sumOfOneCount = dp[i - 1].second + dp[i - 2].second;
		dp[i] = Count(sumOfZeroCount, sumOfOneCount);
	}

	int testCase;
	cin >> testCase;
	for (int i = 0; i < testCase; i++)
	{
		int N;
		cin >> N;
		cout << dp[N].first << " " << dp[N].second << "\n";
	}

	return 0;
}