[백준 1788] 피보나치 수의 확장 (C++)

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

 

문제

---

 𝐹(𝑛):= {0                        if 𝑛=0;

            1                         if 𝑛=1;

            𝐹(𝑛−1) + 𝐹(𝑛−2) if 𝑛>1.}

수학에서, 피보나치 수는 위의 점화식과 같이 귀납적으로 정의되는 수열이다. 위의 식에서도 알 수 있듯이, 피보나치 수 F(n)은 0 이상의 n에 대해서만 정의된다.

하지만 피보나치 수 F(n)을 n이 음수인 경우로도 확장시킬 수 있다. 위의 식에서 n > 1인 경우에만 성립하는 F(n) = F(n-1) + F(n-2)를 n ≤ 1일 때도 성립되도록 정의하는 것이다. 예를 들어 n = 1일 때 F(1) = F(0) + F(-1)이 성립되어야 하므로, F(-1)은 1이 되어야 한다.

n이 주어졌을 때, 피보나치 수 F(n)을 구하는 프로그램을 작성하시오. n은 음수로 주어질 수도 있다.

 

입력

---

첫째 줄에 n이 주어진다. n은 절댓값이 1,000,000을 넘지 않는 정수이다.

 

출력

---

 

첫째 줄에 F(n)이 양수이면 1, 0이면 0, 음수이면 -1을 출력한다. 둘째 줄에는 F(n)의 절댓값을 출력한다. 이 수가 충분히 커질 수 있으므로, 절댓값을 1,000,000,000으로 나눈 나머지를 출력한다.

 

문제 풀이

---

dp 문제.

n이 2이상의 양수라면 F(N) = F(N - 1) + F(N - 2)를 이용하여 F(N)을 구할 수 있다. 피보나치 수를 저장할 dp 배열을 선언한 후 dp[0]=0, dp[1]=1로 초기화한 후 dp[2]부터는 dp[i] = dp[i - 1] + dp[i - 2]를 이용하여 dp[n]까지 채워나간다.

n이 음수인 경우에는 F(N) = F(N - 1) + F(N - 2)에서 F(N - 2) = F(N) - F(N - 1)임을 이용한다. 예시로는 F(-1) = F(1) - F(0)으로 나타낼 수 있으며, F(-2) = F(0) - F(-1)로 나타낼 수 있다. 마찬가지로 피보나치 수를 저장할 dp 배열에 값들을 저장하는데, i번째 인덱스는 F(-i)를 나타낸다. 즉, dp[1] = F(-1), dp[2] = F(-2)를 나타내는 것이다. dp[0] = 0이고, 식에 의해 dp[1] = 1로 초기화된다. dp[2]부터는 dp[i] = dp[i-2]-dp[i-1]임을 이용하여 dp[n]까지 채워나간다.

숫자가 int 타입을 넘어가지 않도록 값을 구하면서 1,000,000,000로 나누어 나머지만을 저장하게 해야 하며, n이 음수일 때 잘못된 배열의 인덱스에 접근하지 않도록 abs(n)을 이용하여 배열에 접근하도록 한다.

 

아래는 코드.

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;
	int* dp = new int[abs(N) + 1];
	if (N >= 0)
	{
		dp[0] = 0;
		dp[1] = 1;
		for (int i = 2; i < N+1; i++)
		{
			dp[i] = dp[i-1] % 1000000000 + dp[i - 2] % 1000000000;
			dp[i] %= 1000000000;
		}
	}
	else
	{
		dp[0] = 0;
		dp[1] = 1;
		for (int i = 2; i < abs(N) + 1; i++)
		{
			dp[i] = dp[i - 2] % 1000000000 - dp[i - 1] % 1000000000;
			dp[i] %= 1000000000;
		}
	}
	if (dp[abs(N)] > 0)
	{
		cout << 1 << "\n";
	}
	else if (dp[abs(N)] == 0)
	{
		cout << 0 << "\n";
	}
	else
	{
		cout << -1 << "\n";
	}
	cout << abs(dp[abs(N)]) << "\n";
	return 0;
}